src/test_rtree.c

   1 /*
   2 ** 2010 August 28
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** Code for testing all sorts of SQLite interfaces. This code
  13 ** is not included in the SQLite library.
  14 */
  15
  16 #include "sqlite3.h"
  17 #if defined(INCLUDE_SQLITE_TCL_H)
  18 #  include "sqlite_tcl.h"
  19 #else
  20 #  include "tcl.h"
  21 #endif
  22
  23 /* Solely for the UNUSED_PARAMETER() macro. */
  24 #include "sqliteInt.h"
  25
  26 #ifdef SQLITE_ENABLE_RTREE
  27 /*
  28 ** Type used to cache parameter information for the "circle" r-tree geometry
  29 ** callback.
  30 */
  31 typedef struct Circle Circle;
  32 struct Circle {
  33   struct Box {
  34     double xmin;
  35     double xmax;
  36     double ymin;
  37     double ymax;
  38   } aBox[2];
  39   double centerx;
  40   double centery;
  41   double radius;
  42   double mxArea;
  43   int eScoreType;
  44 };
  45
  46 /*
  47 ** Destructor function for Circle objects allocated by circle_geom().
  48 */
  49 static void circle_del(void *p){
  50   sqlite3_free(p);
  51 }
  52
  53 /*
  54 ** Implementation of "circle" r-tree geometry callback.
  55 */
  56 static int circle_geom(
  57   sqlite3_rtree_geometry *p,
  58   int nCoord,
  59   sqlite3_rtree_dbl *aCoord,
  60   int *pRes
  61 ){
  62   int i;                          /* Iterator variable */
  63   Circle *pCircle;                /* Structure defining circular region */
  64   double xmin, xmax;              /* X dimensions of box being tested */
  65   double ymin, ymax;              /* X dimensions of box being tested */
  66
  67   xmin = aCoord[0];
  68   xmax = aCoord[1];
  69   ymin = aCoord[2];
  70   ymax = aCoord[3];
  71   pCircle = (Circle *)p->pUser;
  72   if( pCircle==0 ){
  73     /* If pUser is still 0, then the parameter values have not been tested
  74     ** for correctness or stored into a Circle structure yet. Do this now. */
  75
  76     /* This geometry callback is for use with a 2-dimensional r-tree table.
  77     ** Return an error if the table does not have exactly 2 dimensions. */
  78     if( nCoord!=4 ) return SQLITE_ERROR;
  79
  80     /* Test that the correct number of parameters (3) have been supplied,
  81     ** and that the parameters are in range (that the radius of the circle
  82     ** radius is greater than zero). */
  83     if( p->nParam!=3 || p->aParam[2]<0.0 ) return SQLITE_ERROR;
  84
  85     /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM
  86     ** if the allocation fails. */
  87     pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));
  88     if( !pCircle ) return SQLITE_NOMEM;
  89     p->xDelUser = circle_del;
  90
  91     /* Record the center and radius of the circular region. One way that
  92     ** tested bounding boxes that intersect the circular region are detected
  93     ** is by testing if each corner of the bounding box lies within radius
  94     ** units of the center of the circle. */
  95     pCircle->centerx = p->aParam[0];
  96     pCircle->centery = p->aParam[1];
  97     pCircle->radius = p->aParam[2];
  98
  99     /* Define two bounding box regions. The first, aBox[0], extends to
 100     ** infinity in the X dimension. It covers the same range of the Y dimension
 101     ** as the circular region. The second, aBox[1], extends to infinity in
 102     ** the Y dimension and is constrained to the range of the circle in the
 103     ** X dimension.
 104     **
 105     ** Then imagine each box is split in half along its short axis by a line
 106     ** that intersects the center of the circular region. A bounding box
 107     ** being tested can be said to intersect the circular region if it contains
 108     ** points from each half of either of the two infinite bounding boxes.
 109     */
 110     pCircle->aBox[0].xmin = pCircle->centerx;
 111     pCircle->aBox[0].xmax = pCircle->centerx;
 112     pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;
 113     pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;
 114     pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;
 115     pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;
 116     pCircle->aBox[1].ymin = pCircle->centery;
 117     pCircle->aBox[1].ymax = pCircle->centery;
 118     pCircle->mxArea = (xmax - xmin)*(ymax - ymin) + 1.0;
 119   }
 120
 121   /* Check if any of the 4 corners of the bounding-box being tested lie
 122   ** inside the circular region. If they do, then the bounding-box does
 123   ** intersect the region of interest. Set the output variable to true and
 124   ** return SQLITE_OK in this case. */
 125   for(i=0; i<4; i++){
 126     double x = (i&0x01) ? xmax : xmin;
 127     double y = (i&0x02) ? ymax : ymin;
 128     double d2;
 129
 130     d2  = (x-pCircle->centerx)*(x-pCircle->centerx);
 131     d2 += (y-pCircle->centery)*(y-pCircle->centery);
 132     if( d2<(pCircle->radius*pCircle->radius) ){
 133       *pRes = 1;
 134       return SQLITE_OK;
 135     }
 136   }
 137
 138   /* Check if the bounding box covers any other part of the circular region.
 139   ** See comments above for a description of how this test works. If it does
 140   ** cover part of the circular region, set the output variable to true
 141   ** and return SQLITE_OK. */
 142   for(i=0; i<2; i++){
 143     if( xmin<=pCircle->aBox[i].xmin
 144      && xmax>=pCircle->aBox[i].xmax
 145      && ymin<=pCircle->aBox[i].ymin
 146      && ymax>=pCircle->aBox[i].ymax
 147     ){
 148       *pRes = 1;
 149       return SQLITE_OK;
 150     }
 151   }
 152
 153   /* The specified bounding box does not intersect the circular region. Set
 154   ** the output variable to zero and return SQLITE_OK. */
 155   *pRes = 0;
 156   return SQLITE_OK;
 157 }
 158
 159 /*
 160 ** Implementation of "circle" r-tree geometry callback using the
 161 ** 2nd-generation interface that allows scoring.
 162 **
 163 ** Two calling forms:
 164 **
 165 **          Qcircle(X,Y,Radius,eType)        -- All values are doubles
 166 **          Qcircle('x:X y:Y r:R e:ETYPE')   -- Single string parameter
 167 */
 168 static int circle_query_func(sqlite3_rtree_query_info *p){
 169   int i;                          /* Iterator variable */
 170   Circle *pCircle;                /* Structure defining circular region */
 171   double xmin, xmax;              /* X dimensions of box being tested */
 172   double ymin, ymax;              /* X dimensions of box being tested */
 173   int nWithin = 0;                /* Number of corners inside the circle */
 174
 175   xmin = p->aCoord[0];
 176   xmax = p->aCoord[1];
 177   ymin = p->aCoord[2];
 178   ymax = p->aCoord[3];
 179   pCircle = (Circle *)p->pUser;
 180   if( pCircle==0 ){
 181     /* If pUser is still 0, then the parameter values have not been tested
 182     ** for correctness or stored into a Circle structure yet. Do this now. */
 183
 184     /* This geometry callback is for use with a 2-dimensional r-tree table.
 185     ** Return an error if the table does not have exactly 2 dimensions. */
 186     if( p->nCoord!=4 ) return SQLITE_ERROR;
 187
 188     /* Test that the correct number of parameters (1 or 4) have been supplied.
 189     */
 190     if( p->nParam!=4 && p->nParam!=1 ) return SQLITE_ERROR;
 191
 192     /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM
 193     ** if the allocation fails. */
 194     pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));
 195     if( !pCircle ) return SQLITE_NOMEM;
 196     p->xDelUser = circle_del;
 197
 198     /* Record the center and radius of the circular region. One way that
 199     ** tested bounding boxes that intersect the circular region are detected
 200     ** is by testing if each corner of the bounding box lies within radius
 201     ** units of the center of the circle. */
 202     if( p->nParam==4 ){
 203       pCircle->centerx = p->aParam[0];
 204       pCircle->centery = p->aParam[1];
 205       pCircle->radius = p->aParam[2];
 206       pCircle->eScoreType = (int)p->aParam[3];
 207     }else{
 208       const char *z = (const char*)sqlite3_value_text(p->apSqlParam[0]);
 209       pCircle->centerx = 0.0;
 210       pCircle->centery = 0.0;
 211       pCircle->radius = 0.0;
 212       pCircle->eScoreType = 0;
 213       while( z && z[0] ){
 214         if( z[0]=='r' && z[1]==':' ){
 215           pCircle->radius = atof(&z[2]);
 216         }else if( z[0]=='x' && z[1]==':' ){
 217           pCircle->centerx = atof(&z[2]);
 218         }else if( z[0]=='y' && z[1]==':' ){
 219           pCircle->centery = atof(&z[2]);
 220         }else if( z[0]=='e' && z[1]==':' ){
 221           pCircle->eScoreType = (int)atof(&z[2]);
 222         }else if( z[0]==' ' ){
 223           z++;
 224           continue;
 225         }
 226         while( z[0]!=0 && z[0]!=' ' ) z++;
 227         while( z[0]==' ' ) z++;
 228       }
 229     }
 230     if( pCircle->radius<0.0 ){
 231       sqlite3_free(pCircle);
 232       return SQLITE_NOMEM;
 233     }
 234
 235     /* Define two bounding box regions. The first, aBox[0], extends to
 236     ** infinity in the X dimension. It covers the same range of the Y dimension
 237     ** as the circular region. The second, aBox[1], extends to infinity in
 238     ** the Y dimension and is constrained to the range of the circle in the
 239     ** X dimension.
 240     **
 241     ** Then imagine each box is split in half along its short axis by a line
 242     ** that intersects the center of the circular region. A bounding box
 243     ** being tested can be said to intersect the circular region if it contains
 244     ** points from each half of either of the two infinite bounding boxes.
 245     */
 246     pCircle->aBox[0].xmin = pCircle->centerx;
 247     pCircle->aBox[0].xmax = pCircle->centerx;
 248     pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;
 249     pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;
 250     pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;
 251     pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;
 252     pCircle->aBox[1].ymin = pCircle->centery;
 253     pCircle->aBox[1].ymax = pCircle->centery;
 254     pCircle->mxArea = 200.0*200.0;
 255   }
 256
 257   /* Check if any of the 4 corners of the bounding-box being tested lie
 258   ** inside the circular region. If they do, then the bounding-box does
 259   ** intersect the region of interest. Set the output variable to true and
 260   ** return SQLITE_OK in this case. */
 261   for(i=0; i<4; i++){
 262     double x = (i&0x01) ? xmax : xmin;
 263     double y = (i&0x02) ? ymax : ymin;
 264     double d2;
 265
 266     d2  = (x-pCircle->centerx)*(x-pCircle->centerx);
 267     d2 += (y-pCircle->centery)*(y-pCircle->centery);
 268     if( d2<(pCircle->radius*pCircle->radius) ) nWithin++;
 269   }
 270
 271   /* Check if the bounding box covers any other part of the circular region.
 272   ** See comments above for a description of how this test works. If it does
 273   ** cover part of the circular region, set the output variable to true
 274   ** and return SQLITE_OK. */
 275   if( nWithin==0 ){
 276     for(i=0; i<2; i++){
 277       if( xmin<=pCircle->aBox[i].xmin
 278        && xmax>=pCircle->aBox[i].xmax
 279        && ymin<=pCircle->aBox[i].ymin
 280        && ymax>=pCircle->aBox[i].ymax
 281       ){
 282         nWithin = 1;
 283         break;
 284       }
 285     }
 286   }
 287
 288   if( pCircle->eScoreType==1 ){
 289     /* Depth first search */
 290     p->rScore = p->iLevel;
 291   }else if( pCircle->eScoreType==2 ){
 292     /* Breadth first search */
 293     p->rScore = 100 - p->iLevel;
 294   }else if( pCircle->eScoreType==3 ){
 295     /* Depth-first search, except sort the leaf nodes by area with
 296     ** the largest area first */
 297     if( p->iLevel==1 ){
 298       p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;
 299       if( p->rScore<0.01 ) p->rScore = 0.01;
 300     }else{
 301       p->rScore = 0.0;
 302     }
 303   }else if( pCircle->eScoreType==4 ){
 304     /* Depth-first search, except exclude odd rowids */
 305     p->rScore = p->iLevel;
 306     if( p->iRowid&1 ) nWithin = 0;
 307   }else{
 308     /* Breadth-first search, except exclude odd rowids */
 309     p->rScore = 100 - p->iLevel;
 310     if( p->iRowid&1 ) nWithin = 0;
 311   }
 312   if( nWithin==0 ){
 313     p->eWithin = NOT_WITHIN;
 314   }else if( nWithin>=4 ){
 315     p->eWithin = FULLY_WITHIN;
 316   }else{
 317     p->eWithin = PARTLY_WITHIN;
 318   }
 319   return SQLITE_OK;
 320 }
 321 /*
 322 ** Implementation of "breadthfirstsearch" r-tree geometry callback using the
 323 ** 2nd-generation interface that allows scoring.
 324 **
 325 **     ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ...
 326 **
 327 ** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1.
 328 */
 329 static int bfs_query_func(sqlite3_rtree_query_info *p){
 330   double x0,x1,y0,y1;        /* Dimensions of box being tested */
 331   double bx0,bx1,by0,by1;    /* Boundary of the query function */
 332
 333   if( p->nParam!=4 ) return SQLITE_ERROR;
 334   x0 = p->aCoord[0];
 335   x1 = p->aCoord[1];
 336   y0 = p->aCoord[2];
 337   y1 = p->aCoord[3];
 338   bx0 = p->aParam[0];
 339   bx1 = p->aParam[1];
 340   by0 = p->aParam[2];
 341   by1 = p->aParam[3];
 342   p->rScore = 100 - p->iLevel;
 343   if( p->eParentWithin==FULLY_WITHIN ){
 344     p->eWithin = FULLY_WITHIN;
 345   }else if( x0>=bx0 && x1<=bx1 && y0>=by0 && y1<=by1 ){
 346     p->eWithin = FULLY_WITHIN;
 347   }else if( x1>=bx0 && x0<=bx1 && y1>=by0 && y0<=by1 ){
 348     p->eWithin = PARTLY_WITHIN;
 349   }else{
 350     p->eWithin = NOT_WITHIN;
 351   }
 352   return SQLITE_OK;
 353 }
 354
 355 /* END of implementation of "circle" geometry callback.
 356 **************************************************************************
 357 *************************************************************************/
 358
 359 #include <assert.h>
 360 #if defined(INCLUDE_SQLITE_TCL_H)
 361 #  include "sqlite_tcl.h"
 362 #else
 363 #  include "tcl.h"
 364 #endif
 365
 366 typedef struct Cube Cube;
 367 struct Cube {
 368   double x;
 369   double y;
 370   double z;
 371   double width;
 372   double height;
 373   double depth;
 374 };
 375
 376 static void cube_context_free(void *p){
 377   sqlite3_free(p);
 378 }
 379
 380 /*
 381 ** The context pointer registered along with the 'cube' callback is
 382 ** always ((void *)&gHere). This is just to facilitate testing, it is not
 383 ** actually used for anything.
 384 */
 385 static int gHere = 42;
 386
 387 /*
 388 ** Implementation of a simple r-tree geom callback to test for intersection
 389 ** of r-tree rows with a "cube" shape. Cubes are defined by six scalar
 390 ** coordinates as follows:
 391 **
 392 **   cube(x, y, z, width, height, depth)
 393 **
 394 ** The width, height and depth parameters must all be greater than zero.
 395 */
 396 static int cube_geom(
 397   sqlite3_rtree_geometry *p,
 398   int nCoord,
 399   sqlite3_rtree_dbl *aCoord,
 400   int *piRes
 401 ){
 402   Cube *pCube = (Cube *)p->pUser;
 403
 404   assert( p->pContext==(void *)&gHere );
 405
 406   if( pCube==0 ){
 407     if( p->nParam!=6 || nCoord!=6
 408      || p->aParam[3]<=0.0 || p->aParam[4]<=0.0 || p->aParam[5]<=0.0
 409     ){
 410       return SQLITE_ERROR;
 411     }
 412     pCube = (Cube *)sqlite3_malloc(sizeof(Cube));
 413     if( !pCube ){
 414       return SQLITE_NOMEM;
 415     }
 416     pCube->x = p->aParam[0];
 417     pCube->y = p->aParam[1];
 418     pCube->z = p->aParam[2];
 419     pCube->width = p->aParam[3];
 420     pCube->height = p->aParam[4];
 421     pCube->depth = p->aParam[5];
 422
 423     p->pUser = (void *)pCube;
 424     p->xDelUser = cube_context_free;
 425   }
 426
 427   assert( nCoord==6 );
 428   *piRes = 0;
 429   if( aCoord[0]<=(pCube->x+pCube->width)
 430    && aCoord[1]>=pCube->x
 431    && aCoord[2]<=(pCube->y+pCube->height)
 432    && aCoord[3]>=pCube->y
 433    && aCoord[4]<=(pCube->z+pCube->depth)
 434    && aCoord[5]>=pCube->z
 435   ){
 436     *piRes = 1;
 437   }
 438
 439   return SQLITE_OK;
 440 }
 441 #endif /* SQLITE_ENABLE_RTREE */
 442
 443 static int SQLITE_TCLAPI register_cube_geom(
 444   void * clientData,
 445   Tcl_Interp *interp,
 446   int objc,
 447   Tcl_Obj *CONST objv[]
 448 ){
 449 #ifndef SQLITE_ENABLE_RTREE
 450   UNUSED_PARAMETER(clientData);
 451   UNUSED_PARAMETER(interp);
 452   UNUSED_PARAMETER(objc);
 453   UNUSED_PARAMETER(objv);
 454 #else
 455   extern int getDbPointer(Tcl_Interp*, const char*, sqlite3**);
 456   extern const char *sqlite3ErrName(int);
 457   sqlite3 *db;
 458   int rc;
 459
 460   if( objc!=2 ){
 461     Tcl_WrongNumArgs(interp, 1, objv, "DB");
 462     return TCL_ERROR;
 463   }
 464   if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
 465   rc = sqlite3_rtree_geometry_callback(db, "cube", cube_geom, (void *)&gHere);
 466   Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
 467 #endif
 468   return TCL_OK;
 469 }
 470
 471 static int SQLITE_TCLAPI register_circle_geom(
 472   void * clientData,
 473   Tcl_Interp *interp,
 474   int objc,
 475   Tcl_Obj *CONST objv[]
 476 ){
 477 #ifndef SQLITE_ENABLE_RTREE
 478   UNUSED_PARAMETER(clientData);
 479   UNUSED_PARAMETER(interp);
 480   UNUSED_PARAMETER(objc);
 481   UNUSED_PARAMETER(objv);
 482 #else
 483   extern int getDbPointer(Tcl_Interp*, const char*, sqlite3**);
 484   extern const char *sqlite3ErrName(int);
 485   sqlite3 *db;
 486   int rc;
 487
 488   if( objc!=2 ){
 489     Tcl_WrongNumArgs(interp, 1, objv, "DB");
 490     return TCL_ERROR;
 491   }
 492   if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
 493   rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0);
 494   if( rc==SQLITE_OK ){
 495     rc = sqlite3_rtree_query_callback(db, "Qcircle",
 496                                       circle_query_func, 0, 0);
 497   }
 498   if( rc==SQLITE_OK ){
 499     rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch",
 500                                       bfs_query_func, 0, 0);
 501   }
 502   Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
 503 #endif
 504   return TCL_OK;
 505 }
 506
 507 int Sqlitetestrtree_Init(Tcl_Interp *interp){
 508   Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0);
 509   Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0);
 510   return TCL_OK;
 511 }