Tree-M/MT/MTentry.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 "MTentry.h"
#include "MT.h"

tb_function TB_FUNCTION = MIN_R_INCR;

int sizeofEntry() {
        if(sizeofObject()) return(sizeofObject()+3*sizeof(double)+2*sizeof(BOOL));      // compressedEntry is: Object, rmin, rmax, distance, splitted, recomp
        return 0;
}

GiSTpenalty * 
MTentry::Penalty(const GiSTentry &newEntry) const
{
        double retval;
        assert(newEntry.IsA()==MTENTRY_CLASS);
        const MTentry& e=(const MTentry &)newEntry;
        double dist=object().distance(e.object())+e.maxradius();

//      printf("Distance between %s & %s=%f\n", object().name, e.object().name, dist);
        // return area enlargement
        switch(TB_FUNCTION) {
                case MIN_R_INCR: {
                        retval=dist-maxradius();
                        if(retval<0) retval=-maxDist()+dist;
                        // if the entry can fit in (more than) a node without enlarging its radius, we assign it to its nearest node
                        break;
                }
                case MIN_OVERLAP: {
                        retval=0;
                        for (int i=0; i<Node()->NumEntries(); i++) {    // compute total overlap for this node
                                const MTentry& sibling=(const MTentry &)*(*(Node()))[i].Ptr();
                                double cost=sibling.maxradius()+dist-object().distance(sibling.object());

                                retval+=MAX(cost, 0);
                        }
                        break;
                }
        }
//      cout << "Penalty for " << newEntry << " in " << this << " = " << retval << " (distance = " << dist << ")" << endl;
        return new MTpenalty(retval, dist);
}

GiSTpenalty * 
MTentry::Penalty(const GiSTentry &newEntry, MTpenalty *minPenalty) const
// in this case we can avoid to compute some distances by using some stored information:
// minPenalty (the minimum penalty achieved so far),
// newEntry.key->distance (the distance of the entry from the parent of this entry, stored in the SearchMinPenalty method),
// and maxradius.
{
        double retval;
        assert(newEntry.IsA()==MTENTRY_CLASS);
        const MTentry& e=(const MTentry &)newEntry;
        double dist;

//      printf("Distance between %s & %s=%f\n", object().name, e.object().name, dist);
        // return area enlargement
        switch(TB_FUNCTION) {
                case MIN_R_INCR: {
                        if(((MTkey *)newEntry.Key())->distance>0) {     // in this case is possible to prune some entries using triangular inequality
                                double distPen=fabs(((MTkey *)newEntry.Key())->distance-Key()->distance)-maxradius();
                                MTpenalty *tmpPen;

                                if(distPen>=0) tmpPen=new MTpenalty(distPen, 0);
                                else tmpPen=new MTpenalty(distPen+maxradius()-maxDist(), 0);
                                if((minPenalty!=NULL)&&!((*tmpPen)<(*minPenalty))) {
                                        delete tmpPen;
                                        return new MTpenalty(MAXDOUBLE, 0);     // ... and we avoid to compute this distance
                                }
                                delete tmpPen;
                        }
                        dist=object().distance(e.object())+e.maxradius();       // compute the distance
                        retval=dist-maxradius();
                        if(retval<0) retval=-maxDist()+dist;
                        // if the entry can fit in (more than) a node without enlarging its radius, we assign it to its nearest node
                        break;
                }
                case MIN_OVERLAP: {
                        retval=0;
                        dist=object().distance(e.object())+e.maxradius();
                        for (int i=0; i<Node()->NumEntries(); i++) {    // compute total overlap for this node
                                const MTentry& sibling=(const MTentry &)*(*(Node()))[i].Ptr();
                                double cost=sibling.maxradius()+dist-object().distance(sibling.object());

                                retval+=MAX(cost, 0);
                        }
                        break;
                }
        }
//      cout << "Penalty for " << newEntry << " in " << this << " = " << retval << " (distance = " << dist << ")" << endl;
        return new MTpenalty(retval, dist);
}

GiSTcompressedEntry
MTentry::Compress() const
{
        GiSTcompressedEntry compressedEntry;
        double rmin=((MTkey *)key)->minradius(), rmax=((MTkey *)key)->maxradius(), dist=((MTkey *)key)->distance;
        int sizeofObject=((MTkey *)key)->object().CompressedLength();
        BOOL splitted=((MTkey *)key)->splitted, recomp=((MTkey *)key)->recomp;

        compressedEntry.key=new char[CompressedLength()];
        ((MTkey *)key)->object().Compress(compressedEntry.key); // compress the object
        memcpy(compressedEntry.key+sizeofObject, &rmin, sizeof(double));
        memcpy(compressedEntry.key+sizeofObject+sizeof(double), &rmax, sizeof(double));
        memcpy(compressedEntry.key+sizeofObject+2*sizeof(double), &dist, sizeof(double));
        memcpy(compressedEntry.key+sizeofObject+3*sizeof(double), &splitted, sizeof(BOOL));
        memcpy(compressedEntry.key+sizeofObject+3*sizeof(double)+sizeof(BOOL), &recomp, sizeof(BOOL));
//      Object obj(compressedEntry.key);        // decompress the object
        compressedEntry.keyLen=CompressedLength();
        compressedEntry.ptr=ptr;
        return compressedEntry;
}

void
MTentry::Decompress(const GiSTcompressedEntry entry)
{
        Object obj(entry.key);  // decompress the object
        double rmin, rmax, dist;
        int sizeofObject=obj.CompressedLength();
        BOOL splitted, recomp;

        memcpy(&rmin, entry.key+sizeofObject, sizeof(double));
        memcpy(&rmax, entry.key+sizeofObject+sizeof(double), sizeof(double));
        memcpy(&dist, entry.key+sizeofObject+2*sizeof(double), sizeof(double));
        memcpy(&dist, entry.key+sizeofObject+2*sizeof(double), sizeof(double));
        memcpy(&splitted, entry.key+sizeofObject+3*sizeof(double), sizeof(BOOL));
        memcpy(&recomp, entry.key+sizeofObject+3*sizeof(double)+sizeof(BOOL), sizeof(BOOL));
        key=new MTkey(obj, rmin, rmax, dist, splitted, recomp);
        ptr=entry.ptr;
}
Revision:	1.2
Committed:	Sun May 6 03:30:18 2001 UTC (25 years, 4 months ago) by root
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+1 -1 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			#include "MTentry.h"
25			#include "MT.h"
26
27	root	1.2	tb_function TB_FUNCTION = MIN_R_INCR;
28	root	1.1
29			int sizeofEntry() {
30			if(sizeofObject()) return(sizeofObject()+3sizeof(double)+2sizeof(BOOL)); // compressedEntry is: Object, rmin, rmax, distance, splitted, recomp
31			return 0;
32			}
33
34			GiSTpenalty *
35			MTentry::Penalty(const GiSTentry &newEntry) const
36			{
37			double retval;
38			assert(newEntry.IsA()==MTENTRY_CLASS);
39			const MTentry& e=(const MTentry &)newEntry;
40			double dist=object().distance(e.object())+e.maxradius();
41
42			// printf("Distance between %s & %s=%f\n", object().name, e.object().name, dist);
43			// return area enlargement
44			switch(TB_FUNCTION) {
45			case MIN_R_INCR: {
46			retval=dist-maxradius();
47			if(retval<0) retval=-maxDist()+dist;
48			// if the entry can fit in (more than) a node without enlarging its radius, we assign it to its nearest node
49			break;
50			}
51			case MIN_OVERLAP: {
52			retval=0;
53			for (int i=0; i<Node()->NumEntries(); i++) { // compute total overlap for this node
54			const MTentry& sibling=(const MTentry &)((Node()))[i].Ptr();
55			double cost=sibling.maxradius()+dist-object().distance(sibling.object());
56
57			retval+=MAX(cost, 0);
58			}
59			break;
60			}
61			}
62			// cout << "Penalty for " << newEntry << " in " << this << " = " << retval << " (distance = " << dist << ")" << endl;
63			return new MTpenalty(retval, dist);
64			}
65
66			GiSTpenalty *
67			MTentry::Penalty(const GiSTentry &newEntry, MTpenalty *minPenalty) const
68			// in this case we can avoid to compute some distances by using some stored information:
69			// minPenalty (the minimum penalty achieved so far),
70			// newEntry.key->distance (the distance of the entry from the parent of this entry, stored in the SearchMinPenalty method),
71			// and maxradius.
72			{
73			double retval;
74			assert(newEntry.IsA()==MTENTRY_CLASS);
75			const MTentry& e=(const MTentry &)newEntry;
76			double dist;
77
78			// printf("Distance between %s & %s=%f\n", object().name, e.object().name, dist);
79			// return area enlargement
80			switch(TB_FUNCTION) {
81			case MIN_R_INCR: {
82			if(((MTkey *)newEntry.Key())->distance>0) { // in this case is possible to prune some entries using triangular inequality
83			double distPen=fabs(((MTkey *)newEntry.Key())->distance-Key()->distance)-maxradius();
84			MTpenalty *tmpPen;
85
86			if(distPen>=0) tmpPen=new MTpenalty(distPen, 0);
87			else tmpPen=new MTpenalty(distPen+maxradius()-maxDist(), 0);
88			if((minPenalty!=NULL)&&!((tmpPen)<(minPenalty))) {
89			delete tmpPen;
90			return new MTpenalty(MAXDOUBLE, 0); // ... and we avoid to compute this distance
91			}
92			delete tmpPen;
93			}
94			dist=object().distance(e.object())+e.maxradius(); // compute the distance
95			retval=dist-maxradius();
96			if(retval<0) retval=-maxDist()+dist;
97			// if the entry can fit in (more than) a node without enlarging its radius, we assign it to its nearest node
98			break;
99			}
100			case MIN_OVERLAP: {
101			retval=0;
102			dist=object().distance(e.object())+e.maxradius();
103			for (int i=0; i<Node()->NumEntries(); i++) { // compute total overlap for this node
104			const MTentry& sibling=(const MTentry &)((Node()))[i].Ptr();
105			double cost=sibling.maxradius()+dist-object().distance(sibling.object());
106
107			retval+=MAX(cost, 0);
108			}
109			break;
110			}
111			}
112			// cout << "Penalty for " << newEntry << " in " << this << " = " << retval << " (distance = " << dist << ")" << endl;
113			return new MTpenalty(retval, dist);
114			}
115
116			GiSTcompressedEntry
117			MTentry::Compress() const
118			{
119			GiSTcompressedEntry compressedEntry;
120			double rmin=((MTkey )key)->minradius(), rmax=((MTkey )key)->maxradius(), dist=((MTkey *)key)->distance;
121			int sizeofObject=((MTkey *)key)->object().CompressedLength();
122			BOOL splitted=((MTkey )key)->splitted, recomp=((MTkey )key)->recomp;
123
124			compressedEntry.key=new char[CompressedLength()];
125			((MTkey *)key)->object().Compress(compressedEntry.key); // compress the object
126			memcpy(compressedEntry.key+sizeofObject, &rmin, sizeof(double));
127			memcpy(compressedEntry.key+sizeofObject+sizeof(double), &rmax, sizeof(double));
128			memcpy(compressedEntry.key+sizeofObject+2*sizeof(double), &dist, sizeof(double));
129			memcpy(compressedEntry.key+sizeofObject+3*sizeof(double), &splitted, sizeof(BOOL));
130			memcpy(compressedEntry.key+sizeofObject+3*sizeof(double)+sizeof(BOOL), &recomp, sizeof(BOOL));
131			// Object obj(compressedEntry.key); // decompress the object
132			compressedEntry.keyLen=CompressedLength();
133			compressedEntry.ptr=ptr;
134			return compressedEntry;
135			}
136
137			void
138			MTentry::Decompress(const GiSTcompressedEntry entry)
139			{
140			Object obj(entry.key); // decompress the object
141			double rmin, rmax, dist;
142			int sizeofObject=obj.CompressedLength();
143			BOOL splitted, recomp;
144
145			memcpy(&rmin, entry.key+sizeofObject, sizeof(double));
146			memcpy(&rmax, entry.key+sizeofObject+sizeof(double), sizeof(double));
147			memcpy(&dist, entry.key+sizeofObject+2*sizeof(double), sizeof(double));
148			memcpy(&dist, entry.key+sizeofObject+2*sizeof(double), sizeof(double));
149			memcpy(&splitted, entry.key+sizeofObject+3*sizeof(double), sizeof(BOOL));
150			memcpy(&recomp, entry.key+sizeofObject+3*sizeof(double)+sizeof(BOOL), sizeof(BOOL));
151			key=new MTkey(obj, rmin, rmax, dist, splitted, recomp);
152			ptr=entry.ptr;
153			}