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 (23 years ago) by root
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+1 -1 lines
Log Message:	* empty log message *
#	Content
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	tb_function TB_FUNCTION = MIN_R_INCR;
28
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	}