SQLite

#-------------------------------------------------------------------------
# Test the example 2d "circle" geometry callback.
#
register_circle_geom db

do_execsql_test rtreeE-1.1 {
  PRAGMA page_size=512;
  CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1);
  
  /* A tight pattern of small boxes near 0,0 */
  WITH RECURSIVE
    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
  INSERT INTO rt1 SELECT x+5*y, x, x+2, y, y+2 FROM x, y;

  /* A looser pattern of small boxes near 100, 0 */
  WITH RECURSIVE
    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
  INSERT INTO rt1 SELECT 100+x+5*y, x*3+100, x*3+102, y*3, y*3+2 FROM x, y;

  /* A looser pattern of larger boxes near 0, 200 */
  WITH RECURSIVE
    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
  INSERT INTO rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
} {}


# Queries against each of the three clusters */
do_execsql_test rtreeE-1.1 {
  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id;
} {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24}
do_execsql_test rtreeE-1.2 {
  SELECT id FROM rt1 WHERE id MATCH Qcircle(100.0, 0.0, 50.0, 3) ORDER BY id;
} {100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124}
do_execsql_test rtreeE-1.3 {
  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 200.0, 50.0, 3) ORDER BY id;
} {200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224}


# The Qcircle geometry function gives a lower score to larger leaf-nodes.
# This causes the 200s to sort before the 100s and the 0s to sort before
# last.
#
do_execsql_test rtreeE-1.4 {
  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,3) AND id%100==0
} {200 100 0}

# Construct a large 2-D RTree with thousands of random entries.
#
do_test rtreeE-2.1 {
  db eval {
    CREATE TABLE t2(id,x0,x1,y0,y1);
    CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1);
    BEGIN;
  }
  expr srand(0)
  for {set i 1} {$i<=10000} {incr i} {
    set dx [expr {int(rand()*40)+1}]
    set dy [expr {int(rand()*40)+1}]
    set x0 [expr {int(rand()*(10000 - $dx))}]
    set x1 [expr {$x0+$dx}]
    set y0 [expr {int(rand()*(10000 - $dy))}]
    set y1 [expr {$y0+$dy}]
    set id [expr {$i+10000}]
    db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)}
  }
  db eval {
    INSERT INTO rt2 SELECT * FROM t2;
    COMMIT;
  }
} {}

for {set i 1} {$i<=200} {incr i} {
  set dx [expr {int(rand()*100)}]
  set dy [expr {int(rand()*100)}]
  set x0 [expr {int(rand()*(10000 - $dx))}]
  set x1 [expr {$x0+$dx}]
  set y0 [expr {int(rand()*(10000 - $dy))}]
  set y1 [expr {$y0+$dy}]
  set ans [db eval {SELECT id FROM t2 WHERE x1>=$x0 AND x0<=$x1 AND y1>=$y0 AND y0<=$y1 ORDER BY id}]
  do_execsql_test rtreeE-2.2.$i {
    SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ORDER BY id
  } $ans
}

# Run query that have very deep priority queues
#
set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=5000 AND y1>=0 AND y0<=5000 ORDER BY id}]
do_execsql_test rtreeE-2.3 {
  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,5000,0,5000) ORDER BY id
} $ans
set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=10000 AND y1>=0 AND y0<=10000 ORDER BY id}]
do_execsql_test rtreeE-2.4 {
  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,10000,0,10000) ORDER BY id
} $ans

finish_test

    double ymin;
    double ymax;
  } aBox[2];
  double centerx;
  double centery;
  double radius;
  double mxArea;
  int eScoreType;
};

/*
** Destructor function for Circle objects allocated by circle_geom().
*/
static void circle_del(void *p){
  sqlite3_free(p);

    /* If pUser is still 0, then the parameter values have not been tested
    ** for correctness or stored into a Circle structure yet. Do this now. */

    /* This geometry callback is for use with a 2-dimensional r-tree table.
    ** Return an error if the table does not have exactly 2 dimensions. */
    if( p->nCoord!=4 ) return SQLITE_ERROR;

    /* Test that the correct number of parameters (4) have been supplied,
    ** and that the parameters are in range (that the radius of the circle 
    ** radius is greater than zero). */
    if( p->nParam!=4 || p->aParam[2]<0.0 ) return SQLITE_ERROR;

    /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM
    ** if the allocation fails. */
    pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));
    if( !pCircle ) return SQLITE_NOMEM;
    p->xDelUser = circle_del;

    /* Record the center and radius of the circular region. One way that
    ** tested bounding boxes that intersect the circular region are detected
    ** is by testing if each corner of the bounding box lies within radius
    ** units of the center of the circle. */
    pCircle->centerx = p->aParam[0];
    pCircle->centery = p->aParam[1];
    pCircle->radius = p->aParam[2];
    pCircle->eScoreType = (int)p->aParam[3];

    /* Define two bounding box regions. The first, aBox[0], extends to
    ** infinity in the X dimension. It covers the same range of the Y dimension
    ** as the circular region. The second, aBox[1], extends to infinity in
    ** the Y dimension and is constrained to the range of the circle in the
    ** X dimension.
    **

      ){
        nWithin = 1;
        break;
      }
    }
  }

  if( pCircle->eScoreType==1 ){
    /* Depth first search */
    p->rScore = p->iLevel;
  }else if( pCircle->eScoreType==2 ){
    /* Breadth first search */
    p->rScore = 100 - p->iLevel;
  }else{
    /* Depth-first search, except sort the leaf nodes by area with
    ** the largest area first */
    if( p->iLevel==2 ){
      p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;
      if( p->rScore<0.01 ) p->rScore = 0.01;
    }else{
      p->rScore = 0.0;
    }
  }
  if( nWithin==0 ){
    p->eWithin = NOT_WITHIN;
  }else if( nWithin>=4 ){
    p->eWithin = FULLY_WITHIN;
  }else{
    p->eWithin = PARTLY_WITHIN;
  }
  return SQLITE_OK;
}
/*
** Implementation of "breadthfirstsearch" r-tree geometry callback using the 
** 2nd-generation interface that allows scoring.
**
**     ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ...
**
** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1.
*/
static int bfs_query_func(sqlite3_rtree_query_info *p){
  double x0,x1,y0,y1;        /* Dimensions of box being tested */
  double bx0,bx1,by0,by1;    /* Boundary of the query function */

  if( p->nParam!=4 ) return SQLITE_ERROR;
  x0 = p->aCoord[0];
  x1 = p->aCoord[1];
  y0 = p->aCoord[2];
  y1 = p->aCoord[3];
  bx0 = p->aParam[0];
  bx1 = p->aParam[1];
  by0 = p->aParam[2];
  by1 = p->aParam[3];
  p->rScore = 100 - p->iLevel;
  if( p->eParentWithin==FULLY_WITHIN ){
    p->eWithin = FULLY_WITHIN;
  }else if( x0>=bx0 && x1<=bx1 && y0>=by0 && y1<=by1 ){
    p->eWithin = FULLY_WITHIN;
  }else if( x1>=bx0 && x0<=bx1 && y1>=by0 && y0<=by1 ){
    p->eWithin = PARTLY_WITHIN;
  }else{
    p->eWithin = NOT_WITHIN;
  }
  return SQLITE_OK;
}

/* END of implementation of "circle" geometry callback.
**************************************************************************
*************************************************************************/

#include <assert.h>
#include "tcl.h"

  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
  rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0);
  if( rc==SQLITE_OK ){
    rc = sqlite3_rtree_query_callback(db, "Qcircle",
                                      circle_query_func, 0, 0);
  }
  if( rc==SQLITE_OK ){
    rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch",
                                      bfs_query_func, 0, 0);
  }
  Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
#endif
  return TCL_OK;
}

int Sqlitetestrtree_Init(Tcl_Interp *interp){
  Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0);
  Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0);
  return TCL_OK;
}