Tree-M/MT/Main.cpp

/*********************************************************************
*                                                                    *
* 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.                                                       *
*                                                                    *
*********************************************************************/

#include <stdio.h>
#include <fstream.h>
#include <time.h>
#include <malloc.h>
#ifdef UNIX
#include <unistd.h>
#include <ctype.h>
#endif

#include "MT.h"
#include "MTpredicate.h"

#define IndObjs 11648

int compdists;
int IOread, IOwrite;
int objs;
int dimension=2;
double eps;

language query_language=FUZZY_STANDARD;
dist2sim hfunction=LINEAR;

extern double MIN_UTIL;
extern pp_function PROMOTE_PART_FUNCTION;
extern pv_function PROMOTE_VOTE_FUNCTION;
extern pp_function SECONDARY_PART_FUNCTION;
extern r_function RADIUS_FUNCTION;
extern int NUM_CANDIDATES;
extern s_function SPLIT_FUNCTION;

MT *gist=NULL;

int debug=0;

// close the tree and delete it
void
CommandClose()
{
        if(gist) {
                delete gist;
                gist=NULL;
        }
}

// create a new tree and open it
void
CommandCreate(const char *method, const char *table)
{
        CommandClose();
        if(!strcmp(method, "mtree")) gist=new MT;
        else {
                cerr << "The only supported method is mtree.\n";
                return;
        }
        gist->Create(table);
        if(!gist->IsOpen()) {
                cout << "Error opening index.\n";
                delete gist;
                return;
        }
        cout << "Table " << table << " created as type " << method << ".\n";
}

// delete the tree from disk
void
CommandDrop(const char *table)
{
        if (unlink(table)) cout << "There is no table by that name.\n";
        else cout << "Table " << table << " dropped.\n";
}

// open the specified tree
void
CommandOpen(const char *method, const char *table)
{
        CommandClose();
        if(!strcmp(method, "mtree")) gist=new MT;
        else {
                cerr << "The only supported method is mtree.\n";
                return;
        }
        gist->Open(table);
        if(!gist->IsOpen()) {
                delete gist;
                cout << "Error opening table.\n";
                return;
        }
//      cout << "Table " << table << " opened.\n";
}

// execute a nearest neighbor query
void
CommandNearest(const TopQuery &query)
{
//      cout << "Searching " << query.Pred() << "...\n";
        MTentry **results=gist->TopSearch(query);

        for(unsigned int i=0; i<query.k; i++) {
                MTentry *e=results[i];
//              cout << e;
//              cout << e->Ptr() << " ";
                delete e;
                objs++;
        }
//      cout << endl;
        delete []results;
}

// execute a range query
void
CommandSelect(MTquery& query)
{
        GiSTlist<MTentry *> list=gist->RangeSearch(query);

        while(!list.IsEmpty()) {
                MTentry *e=list.RemoveFront();
//              cout << e;
                delete e;
                objs++;
        }
/*#if defined(_DEBUG)
        CMemoryState msOld, msNew, msDif;
        msOld.Checkpoint();
#endif
#if defined(_DEBUG)
        msNew.Checkpoint();
        msDif.Difference(msOld, msNew);
        msDif.DumpStatistics();
#endif */
}

// delete the objects satisfying the predicate
void
CommandDelete(const GiSTpredicate& pred)
{
        gist->Delete(pred);
}

// insert an object in the tree
void
CommandInsert(const MTkey& key, int ptr)
{
        gist->Insert(MTentry(key, (GiSTpage)ptr));
//      cout << key << "->" << ptr << " inserted into " << table << ".\n";
}

// use the BulkLoading alogrithm to create the tree
void
CommandLoad(const char *table, MTentry **data, int n)
{
        CommandDrop(table);
        CommandCreate("mtree", table);
//      if(gist==NULL) printf("M3 NULL!!\n");
        printf("MinUtil=%f\n", MIN_UTIL);
        gist->BulkLoad(data, n, 1, "tmp");
}

// close the tree and exit
void
CommandQuit()
{
        CommandClose();
        cout << "Goodbye.\n";
//      exit(0);
}

// print the prompt
void
CommandPrompt()
{
        cout << "MTree> ";
        cout.flush();
}

// activate the debug mode (currently unavailable)
void
CommandDebug()
{
        debug=!debug;
        cout << "Debugging Output ";
        cout << (debug ? "ON\n" : "OFF\n");
}

// print the help file (currently unavailable)
void
CommandHelp()
{
        ifstream is("MTree.help");
        char c;

        while(is.get(c)) cout << c;
}

// perform a check of the nodes of the tree
void
CommandCheck()
{
        GiSTpath path;
        path.MakeRoot();
        gist->CheckNode(path, NULL);
}

// print a dump of each node of the tree
void
CommandDump()
{
        GiSTpath path;
        path.MakeRoot();
#ifdef PRINTING_OBJECTS
        gist->DumpNode(cout, path);
#endif
}

// collect and print statistics on the tree
void
CommandStats()
{
        gist->CollectStats();
}

int main(int argc, char **argv)
{
        cerr << "Now starting...\n";
        malloc_stats();
        int i=1;
        char cmdLine[15];
        BOOL end=FALSE;

        compdists=IOread=IOwrite=objs=0;
        cout << "**  MTree: An M-Tree based on Generalized Search Trees\n";
        while(strcmp(cmdLine, "quit")) {
                scanf("%s", cmdLine);
                if(!strcmp(cmdLine, "drop")) {
                        CommandDrop("graphs.M3");
                        if(argc<5) {
                                cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                exit(-1);
                        }
                        MIN_UTIL=atof(argv[1]);
                        SPLIT_FUNCTION=(s_function)atoi(argv[2]);
                        PROMOTE_PART_FUNCTION=(pp_function)atoi(argv[3]);
                        SECONDARY_PART_FUNCTION=(pp_function)atoi(argv[4]);
                        if(SECONDARY_PART_FUNCTION==CONFIRMED) {
                                cout << "The secondary promotion function must be an unconfirmed one\n";
                                exit(-1);
                        }
                        if(PROMOTE_PART_FUNCTION==SAMPLING) {
                                if(argc<6) {
                                        cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                        exit(-1);
                                }
                                NUM_CANDIDATES=atoi(argv[5]);
                        }
                        if(PROMOTE_PART_FUNCTION==CONFIRMED) {
                                if(argc<6) {
                                        cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                        exit(-1);
                                }
                                PROMOTE_VOTE_FUNCTION=(pv_function)atoi(argv[5]);
                                if(PROMOTE_VOTE_FUNCTION==SAMPLINGV) {
                                        if(argc<7) {
                                                cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                                exit(-1);
                                        }
                                        NUM_CANDIDATES=atoi(argv[6]);
                                }
                                else if(PROMOTE_VOTE_FUNCTION==mM_RAD) {
                                        if(argc<7) {
                                                cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                                exit(-1);
                                        }
                                        RADIUS_FUNCTION=(r_function)atoi(argv[6]);
                                }
                        }
                        switch(SPLIT_FUNCTION) {
                                case G_HYPERPL:
                                        cout << "G_HYPL, ";
                                        break;
                                case BAL_G_HYPERPL:
                                        cout << "BAL_G_HYPL, ";
                                        break;
                                case BALANCED:
                                        cout << "BAL, ";
                                        break;
                        }
                        switch(PROMOTE_PART_FUNCTION) {
                                case RANDOM:
                                        cout << "RAN_2 ";
                                        break;
                                case MAX_UB_DIST:
                                        cout << "M_UB_d ";
                                        break;
                                case SAMPLING:
                                        cout << "SAMP" << NUM_CANDIDATES << "_2 ";
                                        break;
                                case MIN_RAD:
                                        cout << "m_R_2 ";
                                        break;
                                case MIN_OVERLAPS:
                                        cout << "m_O_2 ";
                                        break;
                                case CONFIRMED:
                                switch(PROMOTE_VOTE_FUNCTION) {
                                        case RANDOMV:
                                                cout << "RAN_1 ";
                                                break;
                                        case SAMPLINGV:
                                                cout << "SAMP" << NUM_CANDIDATES << "_1 ";
                                                break;
                                        case MAX_LB_DIST:
                                                cout << "M_LB_d ";
                                                break;
                                        case mM_RAD:
                                                cout << "mM_";
                                                switch(RADIUS_FUNCTION) {
                                                        case LB:
                                                                cout << "m";
                                                                break;
                                                        case AVG:
                                                                cout << "A";
                                                                break;
                                                        case UB:
                                                                cout << "M";
                                                                break;
                                                }
                                                cout << "_r ";
                                                break;
                                }
                                break;
                        }
                        switch(SECONDARY_PART_FUNCTION) {
                                case RANDOM:
                                        cout << "(RAN_2)\n";
                                        break;
                                case MAX_UB_DIST:
                                        cout << "(M_UB_d)\n";
                                        break;
                                case SAMPLING:
                                        cout << "(SAMP" << NUM_CANDIDATES << "_2)\n";
                                        break;
                                case MIN_RAD:
                                        cout << "(m_R_2)\n";
                                        break;
                                case MIN_OVERLAPS:
                                        cout << "(m_O_2)\n";
                                        break;
                        }
                        CommandCreate("mtree", "graphs.M3");
                }
                else if(!strcmp(cmdLine, "select")) {
                        Object *obj=Read();
                        Pred *pred=new Pred(*obj);
                        double r;

                        scanf("%s", cmdLine);
                        r=atof(cmdLine);

                        SimpleQuery query(pred, r);

                        delete obj;
                        delete pred;
                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        CommandSelect(query);
                        CommandClose();
                }
                else if((!strcmp(cmdLine, "nearest"))||(!strcmp(cmdLine, "farthest"))) {
                        int k;
                        BOOL nearest=strcmp(cmdLine, "farthest");
                        MTpred *pred;
                        Object *obj=Read();

                        scanf("%s", cmdLine);
                        k=atoi(cmdLine);
                        if(nearest) pred=new Pred(*obj);
                        else {
                                MTpred *npred=new Pred(*obj);

                                pred=new NotPred(npred);
                                delete npred;
                        }
//                      eps=atof(argv[1]);
                        TopQuery query(pred, k);

                        delete pred;
                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        CommandNearest(query);
                        CommandClose();
                        delete obj;
                }
                else if(!strcmp(cmdLine, "cursor")) {
                        Object *obj=Read();
                        Pred pred(*obj);

                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        MTcursor cursor(*gist, pred);

                        scanf("%s", cmdLine);
                        while(strcmp(cmdLine, "close")) {
                                if(!strcmp(cmdLine, "next")) {
                                        int k;
                                        GiSTlist<MTentry *> list;

                                        scanf("%s", cmdLine);
                                        k=atoi(cmdLine);

//                                      cout << "Fetching next " << k << " entries...\n";
                                        for(; k>0; k--) list.Append(cursor.Next());
                                        while(!list.IsEmpty()) {
                                                MTentry *e=list.RemoveFront();
//                                              cout << e;
                                                delete e;
                                                objs++;
                                        }
                                }
                                scanf("%s", cmdLine);
                        }
                        delete obj;
                        CommandClose();
                }
/*              else if(!strcmp(cmdLine, "find")) {
                        int n, k, l, oldcompdists, oldIOread, oldobjs;

                        scanf("%s", cmdLine);
                        n=atoi(cmdLine);

                        double **x=(double **)calloc(n, sizeof(double *));
                        for(i=0; i<n; i++) x[i]=(double *)calloc(dimension, sizeof(double));
                        MTpred **p=(MTpred **)calloc(n, sizeof(MTpred *));
                        AndPred **ap=(AndPred **)calloc(n-1, sizeof(AndPred *));

                        for(i=0; i<n; i++) {
                                for(int j=0; j<dimension; j++) {
                                        scanf("%s", cmdLine);
                                        x[i][j]=atof(cmdLine);
                                }
                                if(x[i][0]>=0) {
                                        Object obj(x[i]);
//                                      cout << "obj=" << obj << endl;
                                        p[i]=new Pred(obj);
                                }
                                else {
                                        x[i][0]=-x[i][0];
                                        Object obj(x[i]);
//                                      cout << "obj=" << obj << endl;
                                        Pred *pr=new Pred(obj);
                                        p[i]=new NotPred(pr);
                                        delete pr;
                                }
//                              cout << "pred=" << *p[i] << endl;
                        }
                        if(n==2) cout << "d=" << p[1]->distance(((Pred *)p[0])->obj()) << endl;
                        ap[0]=new AndPred(p[0], p[1]);
                        for(i=1; i<n-1; i++) ap[i]=new AndPred(ap[i-1], p[i+1]);
//                      cout << "Query: " << *ap[n-2] << endl;
                        scanf("%s", cmdLine);
                        k=atoi(cmdLine);
                        compdists=IOread=IOwrite=0;

                        TopQuery q(ap[n-2], k);

                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        CommandNearest(q);
                        cout << "Computed dists=" << compdists << "\nIO reads=" << IOread << "\nIO writes=" << IOwrite << "\nObjs=" << objs << endl;

                        BOOL (*obs)[IndObjs]=new BOOL [n][IndObjs], pass=FALSE;

                        l=-90;
                        do {
                                int j;

                                for(j=0; j<IndObjs; j++)
                                        for(i=0; i<n; i++) obs[i][j]=FALSE;
                                compdists=IOread=IOwrite=objs=0;
                                l+=100;
                                for(i=0; i<n; i++) {
                                        TopQuery qi(p[i], l);
                                        GiSTlist<GiSTobject *> list=gist->TopSearch(qi);

                                        while(!list.IsEmpty()) {
                                                MTentry *e=(MTentry *)list.RemoveFront();

                                                obs[i][e->Ptr()]=TRUE;
                                                delete e;
                                        }
                                }
                                for(j=0; j<IndObjs; j++) {
                                        BOOL check=TRUE;

                                        for(i=0; (i<n)&&check; i++) check=obs[i][j];
                                        if(check) objs++;
                                }
//                              cout << l << "=>" << objs << endl;
                                if(objs>k) {
                                        pass=TRUE;
                                        l-=110;
                                        oldcompdists=compdists;
                                        oldIOread=IOread;
                                        oldobjs=objs;
                                }
                                if(!pass) {
                                        oldcompdists=compdists;
                                        oldIOread=IOread;
                                        oldobjs=objs;
                                }
//                              else if(objs==0) l+=90; // dangerous: could lead to infinite loops...
                        } while(((objs<k)&&!pass)||((objs>k)&&pass));
                        cout << l << "=>" << objs << endl;
                        if(objs<k) cout << "Computed dists=" << oldcompdists << "\nIO reads=" << oldIOread << "\nObjs=" << oldobjs << endl;
                        else cout << "Computed dists=" << compdists << "\nIO reads=" << IOread << "\nObjs=" << objs << endl;
                        delete []obs;
                        for(i=0; i<n; i++) delete x[i];
                        free(x);
                        for(i=0; i<n; i++) delete p[i];
                        free(p);
                        for(i=0; i<n-1; i++) delete ap[i];
                        free(ap);
                        compdists=IOread=IOwrite=objs=0;
                        CommandClose();
                }
*/              else if(!strcmp(cmdLine, "check")) {
                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        CommandCheck();
                        CommandClose();
                }
                else if(!strcmp(cmdLine, "dump")) {
                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        CommandDump();
                        CommandClose();
                }
                else if(!strcmp(cmdLine, "stats")) {
                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        CommandStats();
                        CommandClose();
                }
                else if(!strcmp(cmdLine, "add")) {
                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        scanf("%s", cmdLine);
                        i=atoi(cmdLine);
                        if(argc<5) {
                                cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                exit(-1);
                        }
                        MIN_UTIL=atof(argv[1]);
                        SPLIT_FUNCTION=(s_function)atoi(argv[2]);
                        PROMOTE_PART_FUNCTION=(pp_function)atoi(argv[3]);
                        SECONDARY_PART_FUNCTION=(pp_function)atoi(argv[4]);
                        if(SECONDARY_PART_FUNCTION==CONFIRMED) {
                                cout << "The secondary promotion function must be an unconfirmed one\n";
                                exit(-1);
                        }
                        if(PROMOTE_PART_FUNCTION==SAMPLING) {
                                if(argc<6) {
                                        cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                        exit(-1);
                                }
                                NUM_CANDIDATES=atoi(argv[5]);
                        }
                        if(PROMOTE_PART_FUNCTION==CONFIRMED) {
                                if(argc<6) {
                                        cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                        exit(-1);
                                }
                                PROMOTE_VOTE_FUNCTION=(pv_function)atoi(argv[5]);
                                if(PROMOTE_VOTE_FUNCTION==SAMPLINGV) {
                                        if(argc<7) {
                                                cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                                exit(-1);
                                        }
                                        NUM_CANDIDATES=atoi(argv[6]);
                                }
                                else if(PROMOTE_VOTE_FUNCTION==mM_RAD) {
                                        if(argc<7) {
                                                cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]|[radius_f]))\n";
                                                exit(-1);
                                        }
                                        RADIUS_FUNCTION=(r_function)atoi(argv[6]);
                                }
                        }
                        switch(SPLIT_FUNCTION) {
                                case G_HYPERPL:
                                        cout << "G_HYPL, ";
                                        break;
                                case BAL_G_HYPERPL:
                                        cout << "BAL_G_HYPL, ";
                                        break;
                                case BALANCED:
                                        cout << "BAL, ";
                                        break;
                        }
                        switch(PROMOTE_PART_FUNCTION) {
                                case RANDOM:
                                        cout << "RAN_2 ";
                                        break;
                                case MAX_UB_DIST:
                                        cout << "M_UB_d ";
                                        break;
                                case SAMPLING:
                                        cout << "SAMP" << NUM_CANDIDATES << "_2 ";
                                        break;
                                case MIN_RAD:
                                        cout << "m_R_2 ";
                                        break;
                                case MIN_OVERLAPS:
                                        cout << "m_O_2 ";
                                        break;
                                case CONFIRMED:
                                        switch(PROMOTE_VOTE_FUNCTION) {
                                                case RANDOMV:
                                                        cout << "RAN_1 ";
                                                        break;
                                                case SAMPLINGV:
                                                        cout << "SAMP" << NUM_CANDIDATES << "_1 ";
                                                        break;
                                                case MAX_LB_DIST:
                                                        cout << "M_LB_d ";
                                                        break;
                                                case mM_RAD:
                                                        cout << "mM_";
                                                        switch(RADIUS_FUNCTION) {
                                                                case LB:
                                                                        cout << "m";
                                                                        break;
                                                                case AVG:
                                                                        cout << "A";
                                                                        break;
                                                                case UB:
                                                                        cout << "M";
                                                                        break;
                                                        }
                                                        cout << "_r ";
                                                        break;
                                        }
                                        break;
                        }
                        switch(SECONDARY_PART_FUNCTION) {
                                case RANDOM:
                                        cout << "(RAN_2)\n";
                                        break;
                                case MAX_UB_DIST:
                                        cout << "(M_UB_d)\n";
                                        break;
                                case SAMPLING:
                                        cout << "(SAMP" << NUM_CANDIDATES << "_2)\n";
                                        break;
                                case MIN_RAD:
                                        cout << "(m_R_2)\n";
                                        break;
                                case MIN_OVERLAPS:
                                        cout << "(m_O_2)\n";
                                        break;
                        }
                }
                else if(!strcmp(cmdLine, "insert")) {
                        Object *obj=Read();

                        if(!gist) CommandOpen("mtree", "graphs.M3");
                        CommandInsert(MTkey(*obj, 0, 0), i++);
                        delete obj;
                }
                else if(!strcmp(cmdLine, "load")) {
                        MTentry **entries;
                        int n;

                        if(argc<2) {
                                cout << "Usage is: MTree [min_util]\n";
                                exit(-1);
                        }
                        MIN_UTIL=atof(argv[1]);
                        i=0;
                        scanf("%s", cmdLine);
                        n=atoi(cmdLine);
                        entries=new MTentry*[n];
                        for(i=0; i<n; i++) {
                                Object *obj=Read();

                                entries[i]=new MTentry(MTkey(*obj, 0, 0), i);
                                delete obj;
                        }
                        CommandLoad("graphs.M3", entries, n);
                        for(i=0; i<n; i++) delete entries[i];
                        delete []entries;
                }
        }
        cout << "Computed dists=" << compdists << "\nIO reads=" << IOread << "\nIO writes=" << IOwrite << "\nObjs=" << objs << endl;
        CommandQuit();
        cerr << "Now exiting...\n";
        malloc_stats();
}

Revision:	1.1
Committed:	Sun May 6 00:45:53 2001 UTC (25 years, 4 months ago) by root
Branch:	MAIN
CVS Tags:	HEAD
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			#include <stdio.h>
25			#include <fstream.h>
26			#include <time.h>
27			#include <malloc.h>
28			#ifdef UNIX
29			#include <unistd.h>
30			#include <ctype.h>
31			#endif
32
33			#include "MT.h"
34			#include "MTpredicate.h"
35
36			#define IndObjs 11648
37
38			int compdists;
39			int IOread, IOwrite;
40			int objs;
41			int dimension=2;
42			double eps;
43
44			language query_language=FUZZY_STANDARD;
45			dist2sim hfunction=LINEAR;
46
47			extern double MIN_UTIL;
48			extern pp_function PROMOTE_PART_FUNCTION;
49			extern pv_function PROMOTE_VOTE_FUNCTION;
50			extern pp_function SECONDARY_PART_FUNCTION;
51			extern r_function RADIUS_FUNCTION;
52			extern int NUM_CANDIDATES;
53			extern s_function SPLIT_FUNCTION;
54
55			MT *gist=NULL;
56
57			int debug=0;
58
59			// close the tree and delete it
60			void
61			CommandClose()
62			{
63			if(gist) {
64			delete gist;
65			gist=NULL;
66			}
67			}
68
69			// create a new tree and open it
70			void
71			CommandCreate(const char method, const char table)
72			{
73			CommandClose();
74			if(!strcmp(method, "mtree")) gist=new MT;
75			else {
76			cerr << "The only supported method is mtree.\n";
77			return;
78			}
79			gist->Create(table);
80			if(!gist->IsOpen()) {
81			cout << "Error opening index.\n";
82			delete gist;
83			return;
84			}
85			cout << "Table " << table << " created as type " << method << ".\n";
86			}
87
88			// delete the tree from disk
89			void
90			CommandDrop(const char *table)
91			{
92			if (unlink(table)) cout << "There is no table by that name.\n";
93			else cout << "Table " << table << " dropped.\n";
94			}
95
96			// open the specified tree
97			void
98			CommandOpen(const char method, const char table)
99			{
100			CommandClose();
101			if(!strcmp(method, "mtree")) gist=new MT;
102			else {
103			cerr << "The only supported method is mtree.\n";
104			return;
105			}
106			gist->Open(table);
107			if(!gist->IsOpen()) {
108			delete gist;
109			cout << "Error opening table.\n";
110			return;
111			}
112			// cout << "Table " << table << " opened.\n";
113			}
114
115			// execute a nearest neighbor query
116			void
117			CommandNearest(const TopQuery &query)
118			{
119			// cout << "Searching " << query.Pred() << "...\n";
120			MTentry **results=gist->TopSearch(query);
121
122			for(unsigned int i=0; i<query.k; i++) {
123			MTentry *e=results[i];
124			// cout << e;
125			// cout << e->Ptr() << " ";
126			delete e;
127			objs++;
128			}
129			// cout << endl;
130			delete []results;
131			}
132
133			// execute a range query
134			void
135			CommandSelect(MTquery& query)
136			{
137			GiSTlist<MTentry *> list=gist->RangeSearch(query);
138
139			while(!list.IsEmpty()) {
140			MTentry *e=list.RemoveFront();
141			// cout << e;
142			delete e;
143			objs++;
144			}
145			/*#if defined(_DEBUG)
146			CMemoryState msOld, msNew, msDif;
147			msOld.Checkpoint();
148			#endif
149			#if defined(_DEBUG)
150			msNew.Checkpoint();
151			msDif.Difference(msOld, msNew);
152			msDif.DumpStatistics();
153			#endif */
154			}
155
156			// delete the objects satisfying the predicate
157			void
158			CommandDelete(const GiSTpredicate& pred)
159			{
160			gist->Delete(pred);
161			}
162
163			// insert an object in the tree
164			void
165			CommandInsert(const MTkey& key, int ptr)
166			{
167			gist->Insert(MTentry(key, (GiSTpage)ptr));
168			// cout << key << "->" << ptr << " inserted into " << table << ".\n";
169			}
170
171			// use the BulkLoading alogrithm to create the tree
172			void
173			CommandLoad(const char table, MTentry *data, int n)
174			{
175			CommandDrop(table);
176			CommandCreate("mtree", table);
177			// if(gist==NULL) printf("M3 NULL!!\n");
178			printf("MinUtil=%f\n", MIN_UTIL);
179			gist->BulkLoad(data, n, 1, "tmp");
180			}
181
182			// close the tree and exit
183			void
184			CommandQuit()
185			{
186			CommandClose();
187			cout << "Goodbye.\n";
188			// exit(0);
189			}
190
191			// print the prompt
192			void
193			CommandPrompt()
194			{
195			cout << "MTree> ";
196			cout.flush();
197			}
198
199			// activate the debug mode (currently unavailable)
200			void
201			CommandDebug()
202			{
203			debug=!debug;
204			cout << "Debugging Output ";
205			cout << (debug ? "ON\n" : "OFF\n");
206			}
207
208			// print the help file (currently unavailable)
209			void
210			CommandHelp()
211			{
212			ifstream is("MTree.help");
213			char c;
214
215			while(is.get(c)) cout << c;
216			}
217
218			// perform a check of the nodes of the tree
219			void
220			CommandCheck()
221			{
222			GiSTpath path;
223			path.MakeRoot();
224			gist->CheckNode(path, NULL);
225			}
226
227			// print a dump of each node of the tree
228			void
229			CommandDump()
230			{
231			GiSTpath path;
232			path.MakeRoot();
233			#ifdef PRINTING_OBJECTS
234			gist->DumpNode(cout, path);
235			#endif
236			}
237
238			// collect and print statistics on the tree
239			void
240			CommandStats()
241			{
242			gist->CollectStats();
243			}
244
245			int main(int argc, char **argv)
246			{
247			cerr << "Now starting...\n";
248			malloc_stats();
249			int i=1;
250			char cmdLine[15];
251			BOOL end=FALSE;
252
253			compdists=IOread=IOwrite=objs=0;
254			cout << "** MTree: An M-Tree based on Generalized Search Trees\n";
255			while(strcmp(cmdLine, "quit")) {
256			scanf("%s", cmdLine);
257			if(!strcmp(cmdLine, "drop")) {
258			CommandDrop("graphs.M3");
259			if(argc<5) {
260			cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
261			exit(-1);
262			}
263			MIN_UTIL=atof(argv[1]);
264			SPLIT_FUNCTION=(s_function)atoi(argv[2]);
265			PROMOTE_PART_FUNCTION=(pp_function)atoi(argv[3]);
266			SECONDARY_PART_FUNCTION=(pp_function)atoi(argv[4]);
267			if(SECONDARY_PART_FUNCTION==CONFIRMED) {
268			cout << "The secondary promotion function must be an unconfirmed one\n";
269			exit(-1);
270			}
271			if(PROMOTE_PART_FUNCTION==SAMPLING) {
272			if(argc<6) {
273			cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
274			exit(-1);
275			}
276			NUM_CANDIDATES=atoi(argv[5]);
277			}
278			if(PROMOTE_PART_FUNCTION==CONFIRMED) {
279			if(argc<6) {
280			cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
281			exit(-1);
282			}
283			PROMOTE_VOTE_FUNCTION=(pv_function)atoi(argv[5]);
284			if(PROMOTE_VOTE_FUNCTION==SAMPLINGV) {
285			if(argc<7) {
286			cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
287			exit(-1);
288			}
289			NUM_CANDIDATES=atoi(argv[6]);
290			}
291			else if(PROMOTE_VOTE_FUNCTION==mM_RAD) {
292			if(argc<7) {
293			cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
294			exit(-1);
295			}
296			RADIUS_FUNCTION=(r_function)atoi(argv[6]);
297			}
298			}
299			switch(SPLIT_FUNCTION) {
300			case G_HYPERPL:
301			cout << "G_HYPL, ";
302			break;
303			case BAL_G_HYPERPL:
304			cout << "BAL_G_HYPL, ";
305			break;
306			case BALANCED:
307			cout << "BAL, ";
308			break;
309			}
310			switch(PROMOTE_PART_FUNCTION) {
311			case RANDOM:
312			cout << "RAN_2 ";
313			break;
314			case MAX_UB_DIST:
315			cout << "M_UB_d ";
316			break;
317			case SAMPLING:
318			cout << "SAMP" << NUM_CANDIDATES << "_2 ";
319			break;
320			case MIN_RAD:
321			cout << "m_R_2 ";
322			break;
323			case MIN_OVERLAPS:
324			cout << "m_O_2 ";
325			break;
326			case CONFIRMED:
327			switch(PROMOTE_VOTE_FUNCTION) {
328			case RANDOMV:
329			cout << "RAN_1 ";
330			break;
331			case SAMPLINGV:
332			cout << "SAMP" << NUM_CANDIDATES << "_1 ";
333			break;
334			case MAX_LB_DIST:
335			cout << "M_LB_d ";
336			break;
337			case mM_RAD:
338			cout << "mM_";
339			switch(RADIUS_FUNCTION) {
340			case LB:
341			cout << "m";
342			break;
343			case AVG:
344			cout << "A";
345			break;
346			case UB:
347			cout << "M";
348			break;
349			}
350			cout << "_r ";
351			break;
352			}
353			break;
354			}
355			switch(SECONDARY_PART_FUNCTION) {
356			case RANDOM:
357			cout << "(RAN_2)\n";
358			break;
359			case MAX_UB_DIST:
360			cout << "(M_UB_d)\n";
361			break;
362			case SAMPLING:
363			cout << "(SAMP" << NUM_CANDIDATES << "_2)\n";
364			break;
365			case MIN_RAD:
366			cout << "(m_R_2)\n";
367			break;
368			case MIN_OVERLAPS:
369			cout << "(m_O_2)\n";
370			break;
371			}
372			CommandCreate("mtree", "graphs.M3");
373			}
374			else if(!strcmp(cmdLine, "select")) {
375			Object *obj=Read();
376			Pred pred=new Pred(obj);
377			double r;
378
379			scanf("%s", cmdLine);
380			r=atof(cmdLine);
381
382			SimpleQuery query(pred, r);
383
384			delete obj;
385			delete pred;
386			if(!gist) CommandOpen("mtree", "graphs.M3");
387			CommandSelect(query);
388			CommandClose();
389			}
390			else if((!strcmp(cmdLine, "nearest"))\|\|(!strcmp(cmdLine, "farthest"))) {
391			int k;
392			BOOL nearest=strcmp(cmdLine, "farthest");
393			MTpred *pred;
394			Object *obj=Read();
395
396			scanf("%s", cmdLine);
397			k=atoi(cmdLine);
398			if(nearest) pred=new Pred(*obj);
399			else {
400			MTpred npred=new Pred(obj);
401
402			pred=new NotPred(npred);
403			delete npred;
404			}
405			// eps=atof(argv[1]);
406			TopQuery query(pred, k);
407
408			delete pred;
409			if(!gist) CommandOpen("mtree", "graphs.M3");
410			CommandNearest(query);
411			CommandClose();
412			delete obj;
413			}
414			else if(!strcmp(cmdLine, "cursor")) {
415			Object *obj=Read();
416			Pred pred(*obj);
417
418			if(!gist) CommandOpen("mtree", "graphs.M3");
419			MTcursor cursor(*gist, pred);
420
421			scanf("%s", cmdLine);
422			while(strcmp(cmdLine, "close")) {
423			if(!strcmp(cmdLine, "next")) {
424			int k;
425			GiSTlist<MTentry *> list;
426
427			scanf("%s", cmdLine);
428			k=atoi(cmdLine);
429
430			// cout << "Fetching next " << k << " entries...\n";
431			for(; k>0; k--) list.Append(cursor.Next());
432			while(!list.IsEmpty()) {
433			MTentry *e=list.RemoveFront();
434			// cout << e;
435			delete e;
436			objs++;
437			}
438			}
439			scanf("%s", cmdLine);
440			}
441			delete obj;
442			CommandClose();
443			}
444			/* else if(!strcmp(cmdLine, "find")) {
445			int n, k, l, oldcompdists, oldIOread, oldobjs;
446
447			scanf("%s", cmdLine);
448			n=atoi(cmdLine);
449
450			double x=(double )calloc(n, sizeof(double *));
451			for(i=0; i<n; i++) x[i]=(double *)calloc(dimension, sizeof(double));
452			MTpred p=(MTpred )calloc(n, sizeof(MTpred *));
453			AndPred ap=(AndPred )calloc(n-1, sizeof(AndPred *));
454
455			for(i=0; i<n; i++) {
456			for(int j=0; j<dimension; j++) {
457			scanf("%s", cmdLine);
458			x[i][j]=atof(cmdLine);
459			}
460			if(x[i][0]>=0) {
461			Object obj(x[i]);
462			// cout << "obj=" << obj << endl;
463			p[i]=new Pred(obj);
464			}
465			else {
466			x[i][0]=-x[i][0];
467			Object obj(x[i]);
468			// cout << "obj=" << obj << endl;
469			Pred *pr=new Pred(obj);
470			p[i]=new NotPred(pr);
471			delete pr;
472			}
473			// cout << "pred=" << *p[i] << endl;
474			}
475			if(n==2) cout << "d=" << p[1]->distance(((Pred *)p[0])->obj()) << endl;
476			ap[0]=new AndPred(p[0], p[1]);
477			for(i=1; i<n-1; i++) ap[i]=new AndPred(ap[i-1], p[i+1]);
478			// cout << "Query: " << *ap[n-2] << endl;
479			scanf("%s", cmdLine);
480			k=atoi(cmdLine);
481			compdists=IOread=IOwrite=0;
482
483			TopQuery q(ap[n-2], k);
484
485			if(!gist) CommandOpen("mtree", "graphs.M3");
486			CommandNearest(q);
487			cout << "Computed dists=" << compdists << "\nIO reads=" << IOread << "\nIO writes=" << IOwrite << "\nObjs=" << objs << endl;
488
489			BOOL (*obs)[IndObjs]=new BOOL [n][IndObjs], pass=FALSE;
490
491			l=-90;
492			do {
493			int j;
494
495			for(j=0; j<IndObjs; j++)
496			for(i=0; i<n; i++) obs[i][j]=FALSE;
497			compdists=IOread=IOwrite=objs=0;
498			l+=100;
499			for(i=0; i<n; i++) {
500			TopQuery qi(p[i], l);
501			GiSTlist<GiSTobject *> list=gist->TopSearch(qi);
502
503			while(!list.IsEmpty()) {
504			MTentry e=(MTentry )list.RemoveFront();
505
506			obs[i][e->Ptr()]=TRUE;
507			delete e;
508			}
509			}
510			for(j=0; j<IndObjs; j++) {
511			BOOL check=TRUE;
512
513			for(i=0; (i<n)&&check; i++) check=obs[i][j];
514			if(check) objs++;
515			}
516			// cout << l << "=>" << objs << endl;
517			if(objs>k) {
518			pass=TRUE;
519			l-=110;
520			oldcompdists=compdists;
521			oldIOread=IOread;
522			oldobjs=objs;
523			}
524			if(!pass) {
525			oldcompdists=compdists;
526			oldIOread=IOread;
527			oldobjs=objs;
528			}
529			// else if(objs==0) l+=90; // dangerous: could lead to infinite loops...
530			} while(((objs<k)&&!pass)\|\|((objs>k)&&pass));
531			cout << l << "=>" << objs << endl;
532			if(objs<k) cout << "Computed dists=" << oldcompdists << "\nIO reads=" << oldIOread << "\nObjs=" << oldobjs << endl;
533			else cout << "Computed dists=" << compdists << "\nIO reads=" << IOread << "\nObjs=" << objs << endl;
534			delete []obs;
535			for(i=0; i<n; i++) delete x[i];
536			free(x);
537			for(i=0; i<n; i++) delete p[i];
538			free(p);
539			for(i=0; i<n-1; i++) delete ap[i];
540			free(ap);
541			compdists=IOread=IOwrite=objs=0;
542			CommandClose();
543			}
544			*/ else if(!strcmp(cmdLine, "check")) {
545			if(!gist) CommandOpen("mtree", "graphs.M3");
546			CommandCheck();
547			CommandClose();
548			}
549			else if(!strcmp(cmdLine, "dump")) {
550			if(!gist) CommandOpen("mtree", "graphs.M3");
551			CommandDump();
552			CommandClose();
553			}
554			else if(!strcmp(cmdLine, "stats")) {
555			if(!gist) CommandOpen("mtree", "graphs.M3");
556			CommandStats();
557			CommandClose();
558			}
559			else if(!strcmp(cmdLine, "add")) {
560			if(!gist) CommandOpen("mtree", "graphs.M3");
561			scanf("%s", cmdLine);
562			i=atoi(cmdLine);
563			if(argc<5) {
564			cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
565			exit(-1);
566			}
567			MIN_UTIL=atof(argv[1]);
568			SPLIT_FUNCTION=(s_function)atoi(argv[2]);
569			PROMOTE_PART_FUNCTION=(pp_function)atoi(argv[3]);
570			SECONDARY_PART_FUNCTION=(pp_function)atoi(argv[4]);
571			if(SECONDARY_PART_FUNCTION==CONFIRMED) {
572			cout << "The secondary promotion function must be an unconfirmed one\n";
573			exit(-1);
574			}
575			if(PROMOTE_PART_FUNCTION==SAMPLING) {
576			if(argc<6) {
577			cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
578			exit(-1);
579			}
580			NUM_CANDIDATES=atoi(argv[5]);
581			}
582			if(PROMOTE_PART_FUNCTION==CONFIRMED) {
583			if(argc<6) {
584			cout << "Usage is: MTree [min_util] [split_f] [promote_f] [sec_promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
585			exit(-1);
586			}
587			PROMOTE_VOTE_FUNCTION=(pv_function)atoi(argv[5]);
588			if(PROMOTE_VOTE_FUNCTION==SAMPLINGV) {
589			if(argc<7) {
590			cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
591			exit(-1);
592			}
593			NUM_CANDIDATES=atoi(argv[6]);
594			}
595			else if(PROMOTE_VOTE_FUNCTION==mM_RAD) {
596			if(argc<7) {
597			cout << "Usage is: MTree [min_util] [split_f] [promote_f] ([vote_f] ([n_cand]\|[radius_f]))\n";
598			exit(-1);
599			}
600			RADIUS_FUNCTION=(r_function)atoi(argv[6]);
601			}
602			}
603			switch(SPLIT_FUNCTION) {
604			case G_HYPERPL:
605			cout << "G_HYPL, ";
606			break;
607			case BAL_G_HYPERPL:
608			cout << "BAL_G_HYPL, ";
609			break;
610			case BALANCED:
611			cout << "BAL, ";
612			break;
613			}
614			switch(PROMOTE_PART_FUNCTION) {
615			case RANDOM:
616			cout << "RAN_2 ";
617			break;
618			case MAX_UB_DIST:
619			cout << "M_UB_d ";
620			break;
621			case SAMPLING:
622			cout << "SAMP" << NUM_CANDIDATES << "_2 ";
623			break;
624			case MIN_RAD:
625			cout << "m_R_2 ";
626			break;
627			case MIN_OVERLAPS:
628			cout << "m_O_2 ";
629			break;
630			case CONFIRMED:
631			switch(PROMOTE_VOTE_FUNCTION) {
632			case RANDOMV:
633			cout << "RAN_1 ";
634			break;
635			case SAMPLINGV:
636			cout << "SAMP" << NUM_CANDIDATES << "_1 ";
637			break;
638			case MAX_LB_DIST:
639			cout << "M_LB_d ";
640			break;
641			case mM_RAD:
642			cout << "mM_";
643			switch(RADIUS_FUNCTION) {
644			case LB:
645			cout << "m";
646			break;
647			case AVG:
648			cout << "A";
649			break;
650			case UB:
651			cout << "M";
652			break;
653			}
654			cout << "_r ";
655			break;
656			}
657			break;
658			}
659			switch(SECONDARY_PART_FUNCTION) {
660			case RANDOM:
661			cout << "(RAN_2)\n";
662			break;
663			case MAX_UB_DIST:
664			cout << "(M_UB_d)\n";
665			break;
666			case SAMPLING:
667			cout << "(SAMP" << NUM_CANDIDATES << "_2)\n";
668			break;
669			case MIN_RAD:
670			cout << "(m_R_2)\n";
671			break;
672			case MIN_OVERLAPS:
673			cout << "(m_O_2)\n";
674			break;
675			}
676			}
677			else if(!strcmp(cmdLine, "insert")) {
678			Object *obj=Read();
679
680			if(!gist) CommandOpen("mtree", "graphs.M3");
681			CommandInsert(MTkey(*obj, 0, 0), i++);
682			delete obj;
683			}
684			else if(!strcmp(cmdLine, "load")) {
685			MTentry **entries;
686			int n;
687
688			if(argc<2) {
689			cout << "Usage is: MTree [min_util]\n";
690			exit(-1);
691			}
692			MIN_UTIL=atof(argv[1]);
693			i=0;
694			scanf("%s", cmdLine);
695			n=atoi(cmdLine);
696			entries=new MTentry*[n];
697			for(i=0; i<n; i++) {
698			Object *obj=Read();
699
700			entries[i]=new MTentry(MTkey(*obj, 0, 0), i);
701			delete obj;
702			}
703			CommandLoad("graphs.M3", entries, n);
704			for(i=0; i<n; i++) delete entries[i];
705			delete []entries;
706			}
707			}
708			cout << "Computed dists=" << compdists << "\nIO reads=" << IOread << "\nIO writes=" << IOwrite << "\nObjs=" << objs << endl;
709			CommandQuit();
710			cerr << "Now exiting...\n";
711			malloc_stats();
712			}
713