/ Hex Artifact Content
Login

Artifact fdd8d29ca5165c7857987a2ba263fac5c69e231f:


0000: 2f 2a 0a 2a 2a 20 32 30 31 30 20 41 75 67 75 73  /*.** 2010 Augus
0010: 74 20 32 38 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61  t 28.**.** The a
0020: 75 74 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20  uthor disclaims 
0030: 63 6f 70 79 72 69 67 68 74 20 74 6f 20 74 68 69  copyright to thi
0040: 73 20 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20  s source code.  
0050: 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61  In place of.** a
0060: 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68   legal notice, h
0070: 65 72 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e  ere is a blessin
0080: 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20  g:.**.**    May 
0090: 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20  you do good and 
00a0: 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20  not evil..**    
00b0: 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72  May you find for
00c0: 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75  giveness for you
00d0: 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76  rself and forgiv
00e0: 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20  e others..**    
00f0: 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 66 72  May you share fr
0100: 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69  eely, never taki
0110: 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75  ng more than you
0120: 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a   give..**.******
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 0a 2a 2a 20 43 6f 64 65 20 66 6f 72 20  ***.** Code for 
0180: 74 65 73 74 69 6e 67 20 61 6c 6c 20 73 6f 72 74  testing all sort
0190: 73 20 6f 66 20 53 51 4c 69 74 65 20 69 6e 74 65  s of SQLite inte
01a0: 72 66 61 63 65 73 2e 20 54 68 69 73 20 63 6f 64  rfaces. This cod
01b0: 65 0a 2a 2a 20 69 73 20 6e 6f 74 20 69 6e 63 6c  e.** is not incl
01c0: 75 64 65 64 20 69 6e 20 74 68 65 20 53 51 4c 69  uded in the SQLi
01d0: 74 65 20 6c 69 62 72 61 72 79 2e 20 0a 2a 2f 0a  te library. .*/.
01e0: 0a 23 69 6e 63 6c 75 64 65 20 3c 73 71 6c 69 74  .#include <sqlit
01f0: 65 33 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20 3c  e3.h>.#include <
0200: 74 63 6c 2e 68 3e 0a 0a 2f 2a 20 53 6f 6c 65 6c  tcl.h>../* Solel
0210: 79 20 66 6f 72 20 74 68 65 20 55 4e 55 53 45 44  y for the UNUSED
0220: 5f 50 41 52 41 4d 45 54 45 52 28 29 20 6d 61 63  _PARAMETER() mac
0230: 72 6f 2e 20 2a 2f 0a 23 69 6e 63 6c 75 64 65 20  ro. */.#include 
0240: 22 73 71 6c 69 74 65 49 6e 74 2e 68 22 0a 0a 23  "sqliteInt.h"..#
0250: 69 66 64 65 66 20 53 51 4c 49 54 45 5f 45 4e 41  ifdef SQLITE_ENA
0260: 42 4c 45 5f 52 54 52 45 45 0a 2f 2a 20 0a 2a 2a  BLE_RTREE./* .**
0270: 20 54 79 70 65 20 75 73 65 64 20 74 6f 20 63 61   Type used to ca
0280: 63 68 65 20 70 61 72 61 6d 65 74 65 72 20 69 6e  che parameter in
0290: 66 6f 72 6d 61 74 69 6f 6e 20 66 6f 72 20 74 68  formation for th
02a0: 65 20 22 63 69 72 63 6c 65 22 20 72 2d 74 72 65  e "circle" r-tre
02b0: 65 20 67 65 6f 6d 65 74 72 79 0a 2a 2a 20 63 61  e geometry.** ca
02c0: 6c 6c 62 61 63 6b 2e 0a 2a 2f 0a 74 79 70 65 64  llback..*/.typed
02d0: 65 66 20 73 74 72 75 63 74 20 43 69 72 63 6c 65  ef struct Circle
02e0: 20 43 69 72 63 6c 65 3b 0a 73 74 72 75 63 74 20   Circle;.struct 
02f0: 43 69 72 63 6c 65 20 7b 0a 20 20 73 74 72 75 63  Circle {.  struc
0300: 74 20 42 6f 78 20 7b 0a 20 20 20 20 64 6f 75 62  t Box {.    doub
0310: 6c 65 20 78 6d 69 6e 3b 0a 20 20 20 20 64 6f 75  le xmin;.    dou
0320: 62 6c 65 20 78 6d 61 78 3b 0a 20 20 20 20 64 6f  ble xmax;.    do
0330: 75 62 6c 65 20 79 6d 69 6e 3b 0a 20 20 20 20 64  uble ymin;.    d
0340: 6f 75 62 6c 65 20 79 6d 61 78 3b 0a 20 20 7d 20  ouble ymax;.  } 
0350: 61 42 6f 78 5b 32 5d 3b 0a 20 20 64 6f 75 62 6c  aBox[2];.  doubl
0360: 65 20 63 65 6e 74 65 72 78 3b 0a 20 20 64 6f 75  e centerx;.  dou
0370: 62 6c 65 20 63 65 6e 74 65 72 79 3b 0a 20 20 64  ble centery;.  d
0380: 6f 75 62 6c 65 20 72 61 64 69 75 73 3b 0a 20 20  ouble radius;.  
0390: 64 6f 75 62 6c 65 20 6d 78 41 72 65 61 3b 0a 20  double mxArea;. 
03a0: 20 69 6e 74 20 65 53 63 6f 72 65 54 79 70 65 3b   int eScoreType;
03b0: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 44 65 73 74 72  .};../*.** Destr
03c0: 75 63 74 6f 72 20 66 75 6e 63 74 69 6f 6e 20 66  uctor function f
03d0: 6f 72 20 43 69 72 63 6c 65 20 6f 62 6a 65 63 74  or Circle object
03e0: 73 20 61 6c 6c 6f 63 61 74 65 64 20 62 79 20 63  s allocated by c
03f0: 69 72 63 6c 65 5f 67 65 6f 6d 28 29 2e 0a 2a 2f  ircle_geom()..*/
0400: 0a 73 74 61 74 69 63 20 76 6f 69 64 20 63 69 72  .static void cir
0410: 63 6c 65 5f 64 65 6c 28 76 6f 69 64 20 2a 70 29  cle_del(void *p)
0420: 7b 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65  {.  sqlite3_free
0430: 28 70 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6d  (p);.}../*.** Im
0440: 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20  plementation of 
0450: 22 63 69 72 63 6c 65 22 20 72 2d 74 72 65 65 20  "circle" r-tree 
0460: 67 65 6f 6d 65 74 72 79 20 63 61 6c 6c 62 61 63  geometry callbac
0470: 6b 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  k..*/.static int
0480: 20 63 69 72 63 6c 65 5f 67 65 6f 6d 28 0a 20 20   circle_geom(.  
0490: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67 65  sqlite3_rtree_ge
04a0: 6f 6d 65 74 72 79 20 2a 70 2c 0a 20 20 69 6e 74  ometry *p,.  int
04b0: 20 6e 43 6f 6f 72 64 2c 20 0a 20 20 73 71 6c 69   nCoord, .  sqli
04c0: 74 65 33 5f 72 74 72 65 65 5f 64 62 6c 20 2a 61  te3_rtree_dbl *a
04d0: 43 6f 6f 72 64 2c 0a 20 20 69 6e 74 20 2a 70 52  Coord,.  int *pR
04e0: 65 73 0a 29 7b 0a 20 20 69 6e 74 20 69 3b 20 20  es.){.  int i;  
04f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0500: 20 20 20 20 20 20 20 20 2f 2a 20 49 74 65 72 61          /* Itera
0510: 74 6f 72 20 76 61 72 69 61 62 6c 65 20 2a 2f 0a  tor variable */.
0520: 20 20 43 69 72 63 6c 65 20 2a 70 43 69 72 63 6c    Circle *pCircl
0530: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  e;              
0540: 20 20 2f 2a 20 53 74 72 75 63 74 75 72 65 20 64    /* Structure d
0550: 65 66 69 6e 69 6e 67 20 63 69 72 63 75 6c 61 72  efining circular
0560: 20 72 65 67 69 6f 6e 20 2a 2f 0a 20 20 64 6f 75   region */.  dou
0570: 62 6c 65 20 78 6d 69 6e 2c 20 78 6d 61 78 3b 20  ble xmin, xmax; 
0580: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0590: 58 20 64 69 6d 65 6e 73 69 6f 6e 73 20 6f 66 20  X dimensions of 
05a0: 62 6f 78 20 62 65 69 6e 67 20 74 65 73 74 65 64  box being tested
05b0: 20 2a 2f 0a 20 20 64 6f 75 62 6c 65 20 79 6d 69   */.  double ymi
05c0: 6e 2c 20 79 6d 61 78 3b 20 20 20 20 20 20 20 20  n, ymax;        
05d0: 20 20 20 20 20 20 2f 2a 20 58 20 64 69 6d 65 6e        /* X dimen
05e0: 73 69 6f 6e 73 20 6f 66 20 62 6f 78 20 62 65 69  sions of box bei
05f0: 6e 67 20 74 65 73 74 65 64 20 2a 2f 0a 0a 20 20  ng tested */..  
0600: 78 6d 69 6e 20 3d 20 61 43 6f 6f 72 64 5b 30 5d  xmin = aCoord[0]
0610: 3b 0a 20 20 78 6d 61 78 20 3d 20 61 43 6f 6f 72  ;.  xmax = aCoor
0620: 64 5b 31 5d 3b 0a 20 20 79 6d 69 6e 20 3d 20 61  d[1];.  ymin = a
0630: 43 6f 6f 72 64 5b 32 5d 3b 0a 20 20 79 6d 61 78  Coord[2];.  ymax
0640: 20 3d 20 61 43 6f 6f 72 64 5b 33 5d 3b 0a 20 20   = aCoord[3];.  
0650: 70 43 69 72 63 6c 65 20 3d 20 28 43 69 72 63 6c  pCircle = (Circl
0660: 65 20 2a 29 70 2d 3e 70 55 73 65 72 3b 0a 20 20  e *)p->pUser;.  
0670: 69 66 28 20 70 43 69 72 63 6c 65 3d 3d 30 20 29  if( pCircle==0 )
0680: 7b 0a 20 20 20 20 2f 2a 20 49 66 20 70 55 73 65  {.    /* If pUse
0690: 72 20 69 73 20 73 74 69 6c 6c 20 30 2c 20 74 68  r is still 0, th
06a0: 65 6e 20 74 68 65 20 70 61 72 61 6d 65 74 65 72  en the parameter
06b0: 20 76 61 6c 75 65 73 20 68 61 76 65 20 6e 6f 74   values have not
06c0: 20 62 65 65 6e 20 74 65 73 74 65 64 0a 20 20 20   been tested.   
06d0: 20 2a 2a 20 66 6f 72 20 63 6f 72 72 65 63 74 6e   ** for correctn
06e0: 65 73 73 20 6f 72 20 73 74 6f 72 65 64 20 69 6e  ess or stored in
06f0: 74 6f 20 61 20 43 69 72 63 6c 65 20 73 74 72 75  to a Circle stru
0700: 63 74 75 72 65 20 79 65 74 2e 20 44 6f 20 74 68  cture yet. Do th
0710: 69 73 20 6e 6f 77 2e 20 2a 2f 0a 0a 20 20 20 20  is now. */..    
0720: 2f 2a 20 54 68 69 73 20 67 65 6f 6d 65 74 72 79  /* This geometry
0730: 20 63 61 6c 6c 62 61 63 6b 20 69 73 20 66 6f 72   callback is for
0740: 20 75 73 65 20 77 69 74 68 20 61 20 32 2d 64 69   use with a 2-di
0750: 6d 65 6e 73 69 6f 6e 61 6c 20 72 2d 74 72 65 65  mensional r-tree
0760: 20 74 61 62 6c 65 2e 0a 20 20 20 20 2a 2a 20 52   table..    ** R
0770: 65 74 75 72 6e 20 61 6e 20 65 72 72 6f 72 20 69  eturn an error i
0780: 66 20 74 68 65 20 74 61 62 6c 65 20 64 6f 65 73  f the table does
0790: 20 6e 6f 74 20 68 61 76 65 20 65 78 61 63 74 6c   not have exactl
07a0: 79 20 32 20 64 69 6d 65 6e 73 69 6f 6e 73 2e 20  y 2 dimensions. 
07b0: 2a 2f 0a 20 20 20 20 69 66 28 20 6e 43 6f 6f 72  */.    if( nCoor
07c0: 64 21 3d 34 20 29 20 72 65 74 75 72 6e 20 53 51  d!=4 ) return SQ
07d0: 4c 49 54 45 5f 45 52 52 4f 52 3b 0a 0a 20 20 20  LITE_ERROR;..   
07e0: 20 2f 2a 20 54 65 73 74 20 74 68 61 74 20 74 68   /* Test that th
07f0: 65 20 63 6f 72 72 65 63 74 20 6e 75 6d 62 65 72  e correct number
0800: 20 6f 66 20 70 61 72 61 6d 65 74 65 72 73 20 28   of parameters (
0810: 33 29 20 68 61 76 65 20 62 65 65 6e 20 73 75 70  3) have been sup
0820: 70 6c 69 65 64 2c 0a 20 20 20 20 2a 2a 20 61 6e  plied,.    ** an
0830: 64 20 74 68 61 74 20 74 68 65 20 70 61 72 61 6d  d that the param
0840: 65 74 65 72 73 20 61 72 65 20 69 6e 20 72 61 6e  eters are in ran
0850: 67 65 20 28 74 68 61 74 20 74 68 65 20 72 61 64  ge (that the rad
0860: 69 75 73 20 6f 66 20 74 68 65 20 63 69 72 63 6c  ius of the circl
0870: 65 20 0a 20 20 20 20 2a 2a 20 72 61 64 69 75 73  e .    ** radius
0880: 20 69 73 20 67 72 65 61 74 65 72 20 74 68 61 6e   is greater than
0890: 20 7a 65 72 6f 29 2e 20 2a 2f 0a 20 20 20 20 69   zero). */.    i
08a0: 66 28 20 70 2d 3e 6e 50 61 72 61 6d 21 3d 33 20  f( p->nParam!=3 
08b0: 7c 7c 20 70 2d 3e 61 50 61 72 61 6d 5b 32 5d 3c  || p->aParam[2]<
08c0: 30 2e 30 20 29 20 72 65 74 75 72 6e 20 53 51 4c  0.0 ) return SQL
08d0: 49 54 45 5f 45 52 52 4f 52 3b 0a 0a 20 20 20 20  ITE_ERROR;..    
08e0: 2f 2a 20 41 6c 6c 6f 63 61 74 65 20 61 20 73 74  /* Allocate a st
08f0: 72 75 63 74 75 72 65 20 74 6f 20 63 61 63 68 65  ructure to cache
0900: 20 70 61 72 61 6d 65 74 65 72 20 64 61 74 61 20   parameter data 
0910: 69 6e 2e 20 52 65 74 75 72 6e 20 53 51 4c 49 54  in. Return SQLIT
0920: 45 5f 4e 4f 4d 45 4d 0a 20 20 20 20 2a 2a 20 69  E_NOMEM.    ** i
0930: 66 20 74 68 65 20 61 6c 6c 6f 63 61 74 69 6f 6e  f the allocation
0940: 20 66 61 69 6c 73 2e 20 2a 2f 0a 20 20 20 20 70   fails. */.    p
0950: 43 69 72 63 6c 65 20 3d 20 28 43 69 72 63 6c 65  Circle = (Circle
0960: 20 2a 29 28 70 2d 3e 70 55 73 65 72 20 3d 20 73   *)(p->pUser = s
0970: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 73 69  qlite3_malloc(si
0980: 7a 65 6f 66 28 43 69 72 63 6c 65 29 29 29 3b 0a  zeof(Circle)));.
0990: 20 20 20 20 69 66 28 20 21 70 43 69 72 63 6c 65      if( !pCircle
09a0: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45   ) return SQLITE
09b0: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 70 2d 3e 78  _NOMEM;.    p->x
09c0: 44 65 6c 55 73 65 72 20 3d 20 63 69 72 63 6c 65  DelUser = circle
09d0: 5f 64 65 6c 3b 0a 0a 20 20 20 20 2f 2a 20 52 65  _del;..    /* Re
09e0: 63 6f 72 64 20 74 68 65 20 63 65 6e 74 65 72 20  cord the center 
09f0: 61 6e 64 20 72 61 64 69 75 73 20 6f 66 20 74 68  and radius of th
0a00: 65 20 63 69 72 63 75 6c 61 72 20 72 65 67 69 6f  e circular regio
0a10: 6e 2e 20 4f 6e 65 20 77 61 79 20 74 68 61 74 0a  n. One way that.
0a20: 20 20 20 20 2a 2a 20 74 65 73 74 65 64 20 62 6f      ** tested bo
0a30: 75 6e 64 69 6e 67 20 62 6f 78 65 73 20 74 68 61  unding boxes tha
0a40: 74 20 69 6e 74 65 72 73 65 63 74 20 74 68 65 20  t intersect the 
0a50: 63 69 72 63 75 6c 61 72 20 72 65 67 69 6f 6e 20  circular region 
0a60: 61 72 65 20 64 65 74 65 63 74 65 64 0a 20 20 20  are detected.   
0a70: 20 2a 2a 20 69 73 20 62 79 20 74 65 73 74 69 6e   ** is by testin
0a80: 67 20 69 66 20 65 61 63 68 20 63 6f 72 6e 65 72  g if each corner
0a90: 20 6f 66 20 74 68 65 20 62 6f 75 6e 64 69 6e 67   of the bounding
0aa0: 20 62 6f 78 20 6c 69 65 73 20 77 69 74 68 69 6e   box lies within
0ab0: 20 72 61 64 69 75 73 0a 20 20 20 20 2a 2a 20 75   radius.    ** u
0ac0: 6e 69 74 73 20 6f 66 20 74 68 65 20 63 65 6e 74  nits of the cent
0ad0: 65 72 20 6f 66 20 74 68 65 20 63 69 72 63 6c 65  er of the circle
0ae0: 2e 20 2a 2f 0a 20 20 20 20 70 43 69 72 63 6c 65  . */.    pCircle
0af0: 2d 3e 63 65 6e 74 65 72 78 20 3d 20 70 2d 3e 61  ->centerx = p->a
0b00: 50 61 72 61 6d 5b 30 5d 3b 0a 20 20 20 20 70 43  Param[0];.    pC
0b10: 69 72 63 6c 65 2d 3e 63 65 6e 74 65 72 79 20 3d  ircle->centery =
0b20: 20 70 2d 3e 61 50 61 72 61 6d 5b 31 5d 3b 0a 20   p->aParam[1];. 
0b30: 20 20 20 70 43 69 72 63 6c 65 2d 3e 72 61 64 69     pCircle->radi
0b40: 75 73 20 3d 20 70 2d 3e 61 50 61 72 61 6d 5b 32  us = p->aParam[2
0b50: 5d 3b 0a 0a 20 20 20 20 2f 2a 20 44 65 66 69 6e  ];..    /* Defin
0b60: 65 20 74 77 6f 20 62 6f 75 6e 64 69 6e 67 20 62  e two bounding b
0b70: 6f 78 20 72 65 67 69 6f 6e 73 2e 20 54 68 65 20  ox regions. The 
0b80: 66 69 72 73 74 2c 20 61 42 6f 78 5b 30 5d 2c 20  first, aBox[0], 
0b90: 65 78 74 65 6e 64 73 20 74 6f 0a 20 20 20 20 2a  extends to.    *
0ba0: 2a 20 69 6e 66 69 6e 69 74 79 20 69 6e 20 74 68  * infinity in th
0bb0: 65 20 58 20 64 69 6d 65 6e 73 69 6f 6e 2e 20 49  e X dimension. I
0bc0: 74 20 63 6f 76 65 72 73 20 74 68 65 20 73 61 6d  t covers the sam
0bd0: 65 20 72 61 6e 67 65 20 6f 66 20 74 68 65 20 59  e range of the Y
0be0: 20 64 69 6d 65 6e 73 69 6f 6e 0a 20 20 20 20 2a   dimension.    *
0bf0: 2a 20 61 73 20 74 68 65 20 63 69 72 63 75 6c 61  * as the circula
0c00: 72 20 72 65 67 69 6f 6e 2e 20 54 68 65 20 73 65  r region. The se
0c10: 63 6f 6e 64 2c 20 61 42 6f 78 5b 31 5d 2c 20 65  cond, aBox[1], e
0c20: 78 74 65 6e 64 73 20 74 6f 20 69 6e 66 69 6e 69  xtends to infini
0c30: 74 79 20 69 6e 0a 20 20 20 20 2a 2a 20 74 68 65  ty in.    ** the
0c40: 20 59 20 64 69 6d 65 6e 73 69 6f 6e 20 61 6e 64   Y dimension and
0c50: 20 69 73 20 63 6f 6e 73 74 72 61 69 6e 65 64 20   is constrained 
0c60: 74 6f 20 74 68 65 20 72 61 6e 67 65 20 6f 66 20  to the range of 
0c70: 74 68 65 20 63 69 72 63 6c 65 20 69 6e 20 74 68  the circle in th
0c80: 65 0a 20 20 20 20 2a 2a 20 58 20 64 69 6d 65 6e  e.    ** X dimen
0c90: 73 69 6f 6e 2e 0a 20 20 20 20 2a 2a 0a 20 20 20  sion..    **.   
0ca0: 20 2a 2a 20 54 68 65 6e 20 69 6d 61 67 69 6e 65   ** Then imagine
0cb0: 20 65 61 63 68 20 62 6f 78 20 69 73 20 73 70 6c   each box is spl
0cc0: 69 74 20 69 6e 20 68 61 6c 66 20 61 6c 6f 6e 67  it in half along
0cd0: 20 69 74 73 20 73 68 6f 72 74 20 61 78 69 73 20   its short axis 
0ce0: 62 79 20 61 20 6c 69 6e 65 0a 20 20 20 20 2a 2a  by a line.    **
0cf0: 20 74 68 61 74 20 69 6e 74 65 72 73 65 63 74 73   that intersects
0d00: 20 74 68 65 20 63 65 6e 74 65 72 20 6f 66 20 74   the center of t
0d10: 68 65 20 63 69 72 63 75 6c 61 72 20 72 65 67 69  he circular regi
0d20: 6f 6e 2e 20 41 20 62 6f 75 6e 64 69 6e 67 20 62  on. A bounding b
0d30: 6f 78 0a 20 20 20 20 2a 2a 20 62 65 69 6e 67 20  ox.    ** being 
0d40: 74 65 73 74 65 64 20 63 61 6e 20 62 65 20 73 61  tested can be sa
0d50: 69 64 20 74 6f 20 69 6e 74 65 72 73 65 63 74 20  id to intersect 
0d60: 74 68 65 20 63 69 72 63 75 6c 61 72 20 72 65 67  the circular reg
0d70: 69 6f 6e 20 69 66 20 69 74 20 63 6f 6e 74 61 69  ion if it contai
0d80: 6e 73 0a 20 20 20 20 2a 2a 20 70 6f 69 6e 74 73  ns.    ** points
0d90: 20 66 72 6f 6d 20 65 61 63 68 20 68 61 6c 66 20   from each half 
0da0: 6f 66 20 65 69 74 68 65 72 20 6f 66 20 74 68 65  of either of the
0db0: 20 74 77 6f 20 69 6e 66 69 6e 69 74 65 20 62 6f   two infinite bo
0dc0: 75 6e 64 69 6e 67 20 62 6f 78 65 73 2e 0a 20 20  unding boxes..  
0dd0: 20 20 2a 2f 0a 20 20 20 20 70 43 69 72 63 6c 65    */.    pCircle
0de0: 2d 3e 61 42 6f 78 5b 30 5d 2e 78 6d 69 6e 20 3d  ->aBox[0].xmin =
0df0: 20 70 43 69 72 63 6c 65 2d 3e 63 65 6e 74 65 72   pCircle->center
0e00: 78 3b 0a 20 20 20 20 70 43 69 72 63 6c 65 2d 3e  x;.    pCircle->
0e10: 61 42 6f 78 5b 30 5d 2e 78 6d 61 78 20 3d 20 70  aBox[0].xmax = p
0e20: 43 69 72 63 6c 65 2d 3e 63 65 6e 74 65 72 78 3b  Circle->centerx;
0e30: 0a 20 20 20 20 70 43 69 72 63 6c 65 2d 3e 61 42  .    pCircle->aB
0e40: 6f 78 5b 30 5d 2e 79 6d 69 6e 20 3d 20 70 43 69  ox[0].ymin = pCi
0e50: 72 63 6c 65 2d 3e 63 65 6e 74 65 72 79 20 2b 20  rcle->centery + 
0e60: 70 43 69 72 63 6c 65 2d 3e 72 61 64 69 75 73 3b  pCircle->radius;
0e70: 0a 20 20 20 20 70 43 69 72 63 6c 65 2d 3e 61 42  .    pCircle->aB
0e80: 6f 78 5b 30 5d 2e 79 6d 61 78 20 3d 20 70 43 69  ox[0].ymax = pCi
0e90: 72 63 6c 65 2d 3e 63 65 6e 74 65 72 79 20 2d 20  rcle->centery - 
0ea0: 70 43 69 72 63 6c 65 2d 3e 72 61 64 69 75 73 3b  pCircle->radius;
0eb0: 0a 20 20 20 20 70 43 69 72 63 6c 65 2d 3e 61 42  .    pCircle->aB
0ec0: 6f 78 5b 31 5d 2e 78 6d 69 6e 20 3d 20 70 43 69  ox[1].xmin = pCi
0ed0: 72 63 6c 65 2d 3e 63 65 6e 74 65 72 78 20 2b 20  rcle->centerx + 
0ee0: 70 43 69 72 63 6c 65 2d 3e 72 61 64 69 75 73 3b  pCircle->radius;
0ef0: 0a 20 20 20 20 70 43 69 72 63 6c 65 2d 3e 61 42  .    pCircle->aB
0f00: 6f 78 5b 31 5d 2e 78 6d 61 78 20 3d 20 70 43 69  ox[1].xmax = pCi
0f10: 72 63 6c 65 2d 3e 63 65 6e 74 65 72 78 20 2d 20  rcle->centerx - 
0f20: 70 43 69 72 63 6c 65 2d 3e 72 61 64 69 75 73 3b  pCircle->radius;
0f30: 0a 20 20 20 20 70 43 69 72 63 6c 65 2d 3e 61 42  .    pCircle->aB
0f40: 6f 78 5b 31 5d 2e 79 6d 69 6e 20 3d 20 70 43 69  ox[1].ymin = pCi
0f50: 72 63 6c 65 2d 3e 63 65 6e 74 65 72 79 3b 0a 20  rcle->centery;. 
0f60: 20 20 20 70 43 69 72 63 6c 65 2d 3e 61 42 6f 78     pCircle->aBox
0f70: 5b 31 5d 2e 79 6d 61 78 20 3d 20 70 43 69 72 63  [1].ymax = pCirc
0f80: 6c 65 2d 3e 63 65 6e 74 65 72 79 3b 0a 20 20 20  le->centery;.   
0f90: 20 70 43 69 72 63 6c 65 2d 3e 6d 78 41 72 65 61   pCircle->mxArea
0fa0: 20 3d 20 28 78 6d 61 78 20 2d 20 78 6d 69 6e 29   = (xmax - xmin)
0fb0: 2a 28 79 6d 61 78 20 2d 20 79 6d 69 6e 29 20 2b  *(ymax - ymin) +
0fc0: 20 31 2e 30 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20   1.0;.  }..  /* 
0fd0: 43 68 65 63 6b 20 69 66 20 61 6e 79 20 6f 66 20  Check if any of 
0fe0: 74 68 65 20 34 20 63 6f 72 6e 65 72 73 20 6f 66  the 4 corners of
0ff0: 20 74 68 65 20 62 6f 75 6e 64 69 6e 67 2d 62 6f   the bounding-bo
1000: 78 20 62 65 69 6e 67 20 74 65 73 74 65 64 20 6c  x being tested l
1010: 69 65 20 0a 20 20 2a 2a 20 69 6e 73 69 64 65 20  ie .  ** inside 
1020: 74 68 65 20 63 69 72 63 75 6c 61 72 20 72 65 67  the circular reg
1030: 69 6f 6e 2e 20 49 66 20 74 68 65 79 20 64 6f 2c  ion. If they do,
1040: 20 74 68 65 6e 20 74 68 65 20 62 6f 75 6e 64 69   then the boundi
1050: 6e 67 2d 62 6f 78 20 64 6f 65 73 0a 20 20 2a 2a  ng-box does.  **
1060: 20 69 6e 74 65 72 73 65 63 74 20 74 68 65 20 72   intersect the r
1070: 65 67 69 6f 6e 20 6f 66 20 69 6e 74 65 72 65 73  egion of interes
1080: 74 2e 20 53 65 74 20 74 68 65 20 6f 75 74 70 75  t. Set the outpu
1090: 74 20 76 61 72 69 61 62 6c 65 20 74 6f 20 74 72  t variable to tr
10a0: 75 65 20 61 6e 64 0a 20 20 2a 2a 20 72 65 74 75  ue and.  ** retu
10b0: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 20 69 6e 20  rn SQLITE_OK in 
10c0: 74 68 69 73 20 63 61 73 65 2e 20 2a 2f 0a 20 20  this case. */.  
10d0: 66 6f 72 28 69 3d 30 3b 20 69 3c 34 3b 20 69 2b  for(i=0; i<4; i+
10e0: 2b 29 7b 0a 20 20 20 20 64 6f 75 62 6c 65 20 78  +){.    double x
10f0: 20 3d 20 28 69 26 30 78 30 31 29 20 3f 20 78 6d   = (i&0x01) ? xm
1100: 61 78 20 3a 20 78 6d 69 6e 3b 0a 20 20 20 20 64  ax : xmin;.    d
1110: 6f 75 62 6c 65 20 79 20 3d 20 28 69 26 30 78 30  ouble y = (i&0x0
1120: 32 29 20 3f 20 79 6d 61 78 20 3a 20 79 6d 69 6e  2) ? ymax : ymin
1130: 3b 0a 20 20 20 20 64 6f 75 62 6c 65 20 64 32 3b  ;.    double d2;
1140: 0a 20 20 20 20 0a 20 20 20 20 64 32 20 20 3d 20  .    .    d2  = 
1150: 28 78 2d 70 43 69 72 63 6c 65 2d 3e 63 65 6e 74  (x-pCircle->cent
1160: 65 72 78 29 2a 28 78 2d 70 43 69 72 63 6c 65 2d  erx)*(x-pCircle-
1170: 3e 63 65 6e 74 65 72 78 29 3b 0a 20 20 20 20 64  >centerx);.    d
1180: 32 20 2b 3d 20 28 79 2d 70 43 69 72 63 6c 65 2d  2 += (y-pCircle-
1190: 3e 63 65 6e 74 65 72 79 29 2a 28 79 2d 70 43 69  >centery)*(y-pCi
11a0: 72 63 6c 65 2d 3e 63 65 6e 74 65 72 79 29 3b 0a  rcle->centery);.
11b0: 20 20 20 20 69 66 28 20 64 32 3c 28 70 43 69 72      if( d2<(pCir
11c0: 63 6c 65 2d 3e 72 61 64 69 75 73 2a 70 43 69 72  cle->radius*pCir
11d0: 63 6c 65 2d 3e 72 61 64 69 75 73 29 20 29 7b 0a  cle->radius) ){.
11e0: 20 20 20 20 20 20 2a 70 52 65 73 20 3d 20 31 3b        *pRes = 1;
11f0: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 53 51  .      return SQ
1200: 4c 49 54 45 5f 4f 4b 3b 0a 20 20 20 20 7d 0a 20  LITE_OK;.    }. 
1210: 20 7d 0a 0a 20 20 2f 2a 20 43 68 65 63 6b 20 69   }..  /* Check i
1220: 66 20 74 68 65 20 62 6f 75 6e 64 69 6e 67 20 62  f the bounding b
1230: 6f 78 20 63 6f 76 65 72 73 20 61 6e 79 20 6f 74  ox covers any ot
1240: 68 65 72 20 70 61 72 74 20 6f 66 20 74 68 65 20  her part of the 
1250: 63 69 72 63 75 6c 61 72 20 72 65 67 69 6f 6e 2e  circular region.
1260: 0a 20 20 2a 2a 20 53 65 65 20 63 6f 6d 6d 65 6e  .  ** See commen
1270: 74 73 20 61 62 6f 76 65 20 66 6f 72 20 61 20 64  ts above for a d
1280: 65 73 63 72 69 70 74 69 6f 6e 20 6f 66 20 68 6f  escription of ho
1290: 77 20 74 68 69 73 20 74 65 73 74 20 77 6f 72 6b  w this test work
12a0: 73 2e 20 49 66 20 69 74 20 64 6f 65 73 0a 20 20  s. If it does.  
12b0: 2a 2a 20 63 6f 76 65 72 20 70 61 72 74 20 6f 66  ** cover part of
12c0: 20 74 68 65 20 63 69 72 63 75 6c 61 72 20 72 65   the circular re
12d0: 67 69 6f 6e 2c 20 73 65 74 20 74 68 65 20 6f 75  gion, set the ou
12e0: 74 70 75 74 20 76 61 72 69 61 62 6c 65 20 74 6f  tput variable to
12f0: 20 74 72 75 65 0a 20 20 2a 2a 20 61 6e 64 20 72   true.  ** and r
1300: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 2e  eturn SQLITE_OK.
1310: 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69   */.  for(i=0; i
1320: 3c 32 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66  <2; i++){.    if
1330: 28 20 78 6d 69 6e 3c 3d 70 43 69 72 63 6c 65 2d  ( xmin<=pCircle-
1340: 3e 61 42 6f 78 5b 69 5d 2e 78 6d 69 6e 20 0a 20  >aBox[i].xmin . 
1350: 20 20 20 20 26 26 20 78 6d 61 78 3e 3d 70 43 69      && xmax>=pCi
1360: 72 63 6c 65 2d 3e 61 42 6f 78 5b 69 5d 2e 78 6d  rcle->aBox[i].xm
1370: 61 78 20 0a 20 20 20 20 20 26 26 20 79 6d 69 6e  ax .     && ymin
1380: 3c 3d 70 43 69 72 63 6c 65 2d 3e 61 42 6f 78 5b  <=pCircle->aBox[
1390: 69 5d 2e 79 6d 69 6e 20 0a 20 20 20 20 20 26 26  i].ymin .     &&
13a0: 20 79 6d 61 78 3e 3d 70 43 69 72 63 6c 65 2d 3e   ymax>=pCircle->
13b0: 61 42 6f 78 5b 69 5d 2e 79 6d 61 78 20 0a 20 20  aBox[i].ymax .  
13c0: 20 20 29 7b 0a 20 20 20 20 20 20 2a 70 52 65 73    ){.      *pRes
13d0: 20 3d 20 31 3b 0a 20 20 20 20 20 20 72 65 74 75   = 1;.      retu
13e0: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20  rn SQLITE_OK;.  
13f0: 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 54 68    }.  }..  /* Th
1400: 65 20 73 70 65 63 69 66 69 65 64 20 62 6f 75 6e  e specified boun
1410: 64 69 6e 67 20 62 6f 78 20 64 6f 65 73 20 6e 6f  ding box does no
1420: 74 20 69 6e 74 65 72 73 65 63 74 20 74 68 65 20  t intersect the 
1430: 63 69 72 63 75 6c 61 72 20 72 65 67 69 6f 6e 2e  circular region.
1440: 20 53 65 74 0a 20 20 2a 2a 20 74 68 65 20 6f 75   Set.  ** the ou
1450: 74 70 75 74 20 76 61 72 69 61 62 6c 65 20 74 6f  tput variable to
1460: 20 7a 65 72 6f 20 61 6e 64 20 72 65 74 75 72 6e   zero and return
1470: 20 53 51 4c 49 54 45 5f 4f 4b 2e 20 2a 2f 0a 20   SQLITE_OK. */. 
1480: 20 2a 70 52 65 73 20 3d 20 30 3b 0a 20 20 72 65   *pRes = 0;.  re
1490: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
14a0: 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6d 70 6c 65 6d 65  }../*.** Impleme
14b0: 6e 74 61 74 69 6f 6e 20 6f 66 20 22 63 69 72 63  ntation of "circ
14c0: 6c 65 22 20 72 2d 74 72 65 65 20 67 65 6f 6d 65  le" r-tree geome
14d0: 74 72 79 20 63 61 6c 6c 62 61 63 6b 20 75 73 69  try callback usi
14e0: 6e 67 20 74 68 65 20 0a 2a 2a 20 32 6e 64 2d 67  ng the .** 2nd-g
14f0: 65 6e 65 72 61 74 69 6f 6e 20 69 6e 74 65 72 66  eneration interf
1500: 61 63 65 20 74 68 61 74 20 61 6c 6c 6f 77 73 20  ace that allows 
1510: 73 63 6f 72 69 6e 67 2e 0a 2a 2f 0a 73 74 61 74  scoring..*/.stat
1520: 69 63 20 69 6e 74 20 63 69 72 63 6c 65 5f 71 75  ic int circle_qu
1530: 65 72 79 5f 66 75 6e 63 28 73 71 6c 69 74 65 33  ery_func(sqlite3
1540: 5f 72 74 72 65 65 5f 71 75 65 72 79 5f 69 6e 66  _rtree_query_inf
1550: 6f 20 2a 70 29 7b 0a 20 20 69 6e 74 20 69 3b 20  o *p){.  int i; 
1560: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1570: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 74 65 72           /* Iter
1580: 61 74 6f 72 20 76 61 72 69 61 62 6c 65 20 2a 2f  ator variable */
1590: 0a 20 20 43 69 72 63 6c 65 20 2a 70 43 69 72 63  .  Circle *pCirc
15a0: 6c 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  le;             
15b0: 20 20 20 2f 2a 20 53 74 72 75 63 74 75 72 65 20     /* Structure 
15c0: 64 65 66 69 6e 69 6e 67 20 63 69 72 63 75 6c 61  defining circula
15d0: 72 20 72 65 67 69 6f 6e 20 2a 2f 0a 20 20 64 6f  r region */.  do
15e0: 75 62 6c 65 20 78 6d 69 6e 2c 20 78 6d 61 78 3b  uble xmin, xmax;
15f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1600: 20 58 20 64 69 6d 65 6e 73 69 6f 6e 73 20 6f 66   X dimensions of
1610: 20 62 6f 78 20 62 65 69 6e 67 20 74 65 73 74 65   box being teste
1620: 64 20 2a 2f 0a 20 20 64 6f 75 62 6c 65 20 79 6d  d */.  double ym
1630: 69 6e 2c 20 79 6d 61 78 3b 20 20 20 20 20 20 20  in, ymax;       
1640: 20 20 20 20 20 20 20 2f 2a 20 58 20 64 69 6d 65         /* X dime
1650: 6e 73 69 6f 6e 73 20 6f 66 20 62 6f 78 20 62 65  nsions of box be
1660: 69 6e 67 20 74 65 73 74 65 64 20 2a 2f 0a 20 20  ing tested */.  
1670: 69 6e 74 20 6e 57 69 74 68 69 6e 20 3d 20 30 3b  int nWithin = 0;
1680: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1690: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 63 6f 72  /* Number of cor
16a0: 6e 65 72 73 20 69 6e 73 69 64 65 20 74 68 65 20  ners inside the 
16b0: 63 69 72 63 6c 65 20 2a 2f 0a 0a 20 20 78 6d 69  circle */..  xmi
16c0: 6e 20 3d 20 70 2d 3e 61 43 6f 6f 72 64 5b 30 5d  n = p->aCoord[0]
16d0: 3b 0a 20 20 78 6d 61 78 20 3d 20 70 2d 3e 61 43  ;.  xmax = p->aC
16e0: 6f 6f 72 64 5b 31 5d 3b 0a 20 20 79 6d 69 6e 20  oord[1];.  ymin 
16f0: 3d 20 70 2d 3e 61 43 6f 6f 72 64 5b 32 5d 3b 0a  = p->aCoord[2];.
1700: 20 20 79 6d 61 78 20 3d 20 70 2d 3e 61 43 6f 6f    ymax = p->aCoo
1710: 72 64 5b 33 5d 3b 0a 20 20 70 43 69 72 63 6c 65  rd[3];.  pCircle
1720: 20 3d 20 28 43 69 72 63 6c 65 20 2a 29 70 2d 3e   = (Circle *)p->
1730: 70 55 73 65 72 3b 0a 20 20 69 66 28 20 70 43 69  pUser;.  if( pCi
1740: 72 63 6c 65 3d 3d 30 20 29 7b 0a 20 20 20 20 2f  rcle==0 ){.    /
1750: 2a 20 49 66 20 70 55 73 65 72 20 69 73 20 73 74  * If pUser is st
1760: 69 6c 6c 20 30 2c 20 74 68 65 6e 20 74 68 65 20  ill 0, then the 
1770: 70 61 72 61 6d 65 74 65 72 20 76 61 6c 75 65 73  parameter values
1780: 20 68 61 76 65 20 6e 6f 74 20 62 65 65 6e 20 74   have not been t
1790: 65 73 74 65 64 0a 20 20 20 20 2a 2a 20 66 6f 72  ested.    ** for
17a0: 20 63 6f 72 72 65 63 74 6e 65 73 73 20 6f 72 20   correctness or 
17b0: 73 74 6f 72 65 64 20 69 6e 74 6f 20 61 20 43 69  stored into a Ci
17c0: 72 63 6c 65 20 73 74 72 75 63 74 75 72 65 20 79  rcle structure y
17d0: 65 74 2e 20 44 6f 20 74 68 69 73 20 6e 6f 77 2e  et. Do this now.
17e0: 20 2a 2f 0a 0a 20 20 20 20 2f 2a 20 54 68 69 73   */..    /* This
17f0: 20 67 65 6f 6d 65 74 72 79 20 63 61 6c 6c 62 61   geometry callba
1800: 63 6b 20 69 73 20 66 6f 72 20 75 73 65 20 77 69  ck is for use wi
1810: 74 68 20 61 20 32 2d 64 69 6d 65 6e 73 69 6f 6e  th a 2-dimension
1820: 61 6c 20 72 2d 74 72 65 65 20 74 61 62 6c 65 2e  al r-tree table.
1830: 0a 20 20 20 20 2a 2a 20 52 65 74 75 72 6e 20 61  .    ** Return a
1840: 6e 20 65 72 72 6f 72 20 69 66 20 74 68 65 20 74  n error if the t
1850: 61 62 6c 65 20 64 6f 65 73 20 6e 6f 74 20 68 61  able does not ha
1860: 76 65 20 65 78 61 63 74 6c 79 20 32 20 64 69 6d  ve exactly 2 dim
1870: 65 6e 73 69 6f 6e 73 2e 20 2a 2f 0a 20 20 20 20  ensions. */.    
1880: 69 66 28 20 70 2d 3e 6e 43 6f 6f 72 64 21 3d 34  if( p->nCoord!=4
1890: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45   ) return SQLITE
18a0: 5f 45 52 52 4f 52 3b 0a 0a 20 20 20 20 2f 2a 20  _ERROR;..    /* 
18b0: 54 65 73 74 20 74 68 61 74 20 74 68 65 20 63 6f  Test that the co
18c0: 72 72 65 63 74 20 6e 75 6d 62 65 72 20 6f 66 20  rrect number of 
18d0: 70 61 72 61 6d 65 74 65 72 73 20 28 34 29 20 68  parameters (4) h
18e0: 61 76 65 20 62 65 65 6e 20 73 75 70 70 6c 69 65  ave been supplie
18f0: 64 2c 0a 20 20 20 20 2a 2a 20 61 6e 64 20 74 68  d,.    ** and th
1900: 61 74 20 74 68 65 20 70 61 72 61 6d 65 74 65 72  at the parameter
1910: 73 20 61 72 65 20 69 6e 20 72 61 6e 67 65 20 28  s are in range (
1920: 74 68 61 74 20 74 68 65 20 72 61 64 69 75 73 20  that the radius 
1930: 6f 66 20 74 68 65 20 63 69 72 63 6c 65 20 0a 20  of the circle . 
1940: 20 20 20 2a 2a 20 72 61 64 69 75 73 20 69 73 20     ** radius is 
1950: 67 72 65 61 74 65 72 20 74 68 61 6e 20 7a 65 72  greater than zer
1960: 6f 29 2e 20 2a 2f 0a 20 20 20 20 69 66 28 20 70  o). */.    if( p
1970: 2d 3e 6e 50 61 72 61 6d 21 3d 34 20 7c 7c 20 70  ->nParam!=4 || p
1980: 2d 3e 61 50 61 72 61 6d 5b 32 5d 3c 30 2e 30 20  ->aParam[2]<0.0 
1990: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  ) return SQLITE_
19a0: 45 52 52 4f 52 3b 0a 0a 20 20 20 20 2f 2a 20 41  ERROR;..    /* A
19b0: 6c 6c 6f 63 61 74 65 20 61 20 73 74 72 75 63 74  llocate a struct
19c0: 75 72 65 20 74 6f 20 63 61 63 68 65 20 70 61 72  ure to cache par
19d0: 61 6d 65 74 65 72 20 64 61 74 61 20 69 6e 2e 20  ameter data in. 
19e0: 52 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f  Return SQLITE_NO
19f0: 4d 45 4d 0a 20 20 20 20 2a 2a 20 69 66 20 74 68  MEM.    ** if th
1a00: 65 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 66 61 69  e allocation fai
1a10: 6c 73 2e 20 2a 2f 0a 20 20 20 20 70 43 69 72 63  ls. */.    pCirc
1a20: 6c 65 20 3d 20 28 43 69 72 63 6c 65 20 2a 29 28  le = (Circle *)(
1a30: 70 2d 3e 70 55 73 65 72 20 3d 20 73 71 6c 69 74  p->pUser = sqlit
1a40: 65 33 5f 6d 61 6c 6c 6f 63 28 73 69 7a 65 6f 66  e3_malloc(sizeof
1a50: 28 43 69 72 63 6c 65 29 29 29 3b 0a 20 20 20 20  (Circle)));.    
1a60: 69 66 28 20 21 70 43 69 72 63 6c 65 20 29 20 72  if( !pCircle ) r
1a70: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
1a80: 45 4d 3b 0a 20 20 20 20 70 2d 3e 78 44 65 6c 55  EM;.    p->xDelU
1a90: 73 65 72 20 3d 20 63 69 72 63 6c 65 5f 64 65 6c  ser = circle_del
1aa0: 3b 0a 0a 20 20 20 20 2f 2a 20 52 65 63 6f 72 64  ;..    /* Record
1ab0: 20 74 68 65 20 63 65 6e 74 65 72 20 61 6e 64 20   the center and 
1ac0: 72 61 64 69 75 73 20 6f 66 20 74 68 65 20 63 69  radius of the ci
1ad0: 72 63 75 6c 61 72 20 72 65 67 69 6f 6e 2e 20 4f  rcular region. O
1ae0: 6e 65 20 77 61 79 20 74 68 61 74 0a 20 20 20 20  ne way that.    
1af0: 2a 2a 20 74 65 73 74 65 64 20 62 6f 75 6e 64 69  ** tested boundi
1b00: 6e 67 20 62 6f 78 65 73 20 74 68 61 74 20 69 6e  ng boxes that in
1b10: 74 65 72 73 65 63 74 20 74 68 65 20 63 69 72 63  tersect the circ
1b20: 75 6c 61 72 20 72 65 67 69 6f 6e 20 61 72 65 20  ular region are 
1b30: 64 65 74 65 63 74 65 64 0a 20 20 20 20 2a 2a 20  detected.    ** 
1b40: 69 73 20 62 79 20 74 65 73 74 69 6e 67 20 69 66  is by testing if
1b50: 20 65 61 63 68 20 63 6f 72 6e 65 72 20 6f 66 20   each corner of 
1b60: 74 68 65 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78  the bounding box
1b70: 20 6c 69 65 73 20 77 69 74 68 69 6e 20 72 61 64   lies within rad
1b80: 69 75 73 0a 20 20 20 20 2a 2a 20 75 6e 69 74 73  ius.    ** units
1b90: 20 6f 66 20 74 68 65 20 63 65 6e 74 65 72 20 6f   of the center o
1ba0: 66 20 74 68 65 20 63 69 72 63 6c 65 2e 20 2a 2f  f the circle. */
1bb0: 0a 20 20 20 20 70 43 69 72 63 6c 65 2d 3e 63 65  .    pCircle->ce
1bc0: 6e 74 65 72 78 20 3d 20 70 2d 3e 61 50 61 72 61  nterx = p->aPara
1bd0: 6d 5b 30 5d 3b 0a 20 20 20 20 70 43 69 72 63 6c  m[0];.    pCircl
1be0: 65 2d 3e 63 65 6e 74 65 72 79 20 3d 20 70 2d 3e  e->centery = p->
1bf0: 61 50 61 72 61 6d 5b 31 5d 3b 0a 20 20 20 20 70  aParam[1];.    p
1c00: 43 69 72 63 6c 65 2d 3e 72 61 64 69 75 73 20 3d  Circle->radius =
1c10: 20 70 2d 3e 61 50 61 72 61 6d 5b 32 5d 3b 0a 20   p->aParam[2];. 
1c20: 20 20 20 70 43 69 72 63 6c 65 2d 3e 65 53 63 6f     pCircle->eSco
1c30: 72 65 54 79 70 65 20 3d 20 28 69 6e 74 29 70 2d  reType = (int)p-
1c40: 3e 61 50 61 72 61 6d 5b 33 5d 3b 0a 0a 20 20 20  >aParam[3];..   
1c50: 20 2f 2a 20 44 65 66 69 6e 65 20 74 77 6f 20 62   /* Define two b
1c60: 6f 75 6e 64 69 6e 67 20 62 6f 78 20 72 65 67 69  ounding box regi
1c70: 6f 6e 73 2e 20 54 68 65 20 66 69 72 73 74 2c 20  ons. The first, 
1c80: 61 42 6f 78 5b 30 5d 2c 20 65 78 74 65 6e 64 73  aBox[0], extends
1c90: 20 74 6f 0a 20 20 20 20 2a 2a 20 69 6e 66 69 6e   to.    ** infin
1ca0: 69 74 79 20 69 6e 20 74 68 65 20 58 20 64 69 6d  ity in the X dim
1cb0: 65 6e 73 69 6f 6e 2e 20 49 74 20 63 6f 76 65 72  ension. It cover
1cc0: 73 20 74 68 65 20 73 61 6d 65 20 72 61 6e 67 65  s the same range
1cd0: 20 6f 66 20 74 68 65 20 59 20 64 69 6d 65 6e 73   of the Y dimens
1ce0: 69 6f 6e 0a 20 20 20 20 2a 2a 20 61 73 20 74 68  ion.    ** as th
1cf0: 65 20 63 69 72 63 75 6c 61 72 20 72 65 67 69 6f  e circular regio
1d00: 6e 2e 20 54 68 65 20 73 65 63 6f 6e 64 2c 20 61  n. The second, a
1d10: 42 6f 78 5b 31 5d 2c 20 65 78 74 65 6e 64 73 20  Box[1], extends 
1d20: 74 6f 20 69 6e 66 69 6e 69 74 79 20 69 6e 0a 20  to infinity in. 
1d30: 20 20 20 2a 2a 20 74 68 65 20 59 20 64 69 6d 65     ** the Y dime
1d40: 6e 73 69 6f 6e 20 61 6e 64 20 69 73 20 63 6f 6e  nsion and is con
1d50: 73 74 72 61 69 6e 65 64 20 74 6f 20 74 68 65 20  strained to the 
1d60: 72 61 6e 67 65 20 6f 66 20 74 68 65 20 63 69 72  range of the cir
1d70: 63 6c 65 20 69 6e 20 74 68 65 0a 20 20 20 20 2a  cle in the.    *
1d80: 2a 20 58 20 64 69 6d 65 6e 73 69 6f 6e 2e 0a 20  * X dimension.. 
1d90: 20 20 20 2a 2a 0a 20 20 20 20 2a 2a 20 54 68 65     **.    ** The
1da0: 6e 20 69 6d 61 67 69 6e 65 20 65 61 63 68 20 62  n imagine each b
1db0: 6f 78 20 69 73 20 73 70 6c 69 74 20 69 6e 20 68  ox is split in h
1dc0: 61 6c 66 20 61 6c 6f 6e 67 20 69 74 73 20 73 68  alf along its sh
1dd0: 6f 72 74 20 61 78 69 73 20 62 79 20 61 20 6c 69  ort axis by a li
1de0: 6e 65 0a 20 20 20 20 2a 2a 20 74 68 61 74 20 69  ne.    ** that i
1df0: 6e 74 65 72 73 65 63 74 73 20 74 68 65 20 63 65  ntersects the ce
1e00: 6e 74 65 72 20 6f 66 20 74 68 65 20 63 69 72 63  nter of the circ
1e10: 75 6c 61 72 20 72 65 67 69 6f 6e 2e 20 41 20 62  ular region. A b
1e20: 6f 75 6e 64 69 6e 67 20 62 6f 78 0a 20 20 20 20  ounding box.    
1e30: 2a 2a 20 62 65 69 6e 67 20 74 65 73 74 65 64 20  ** being tested 
1e40: 63 61 6e 20 62 65 20 73 61 69 64 20 74 6f 20 69  can be said to i
1e50: 6e 74 65 72 73 65 63 74 20 74 68 65 20 63 69 72  ntersect the cir
1e60: 63 75 6c 61 72 20 72 65 67 69 6f 6e 20 69 66 20  cular region if 
1e70: 69 74 20 63 6f 6e 74 61 69 6e 73 0a 20 20 20 20  it contains.    
1e80: 2a 2a 20 70 6f 69 6e 74 73 20 66 72 6f 6d 20 65  ** points from e
1e90: 61 63 68 20 68 61 6c 66 20 6f 66 20 65 69 74 68  ach half of eith
1ea0: 65 72 20 6f 66 20 74 68 65 20 74 77 6f 20 69 6e  er of the two in
1eb0: 66 69 6e 69 74 65 20 62 6f 75 6e 64 69 6e 67 20  finite bounding 
1ec0: 62 6f 78 65 73 2e 0a 20 20 20 20 2a 2f 0a 20 20  boxes..    */.  
1ed0: 20 20 70 43 69 72 63 6c 65 2d 3e 61 42 6f 78 5b    pCircle->aBox[
1ee0: 30 5d 2e 78 6d 69 6e 20 3d 20 70 43 69 72 63 6c  0].xmin = pCircl
1ef0: 65 2d 3e 63 65 6e 74 65 72 78 3b 0a 20 20 20 20  e->centerx;.    
1f00: 70 43 69 72 63 6c 65 2d 3e 61 42 6f 78 5b 30 5d  pCircle->aBox[0]
1f10: 2e 78 6d 61 78 20 3d 20 70 43 69 72 63 6c 65 2d  .xmax = pCircle-
1f20: 3e 63 65 6e 74 65 72 78 3b 0a 20 20 20 20 70 43  >centerx;.    pC
1f30: 69 72 63 6c 65 2d 3e 61 42 6f 78 5b 30 5d 2e 79  ircle->aBox[0].y
1f40: 6d 69 6e 20 3d 20 70 43 69 72 63 6c 65 2d 3e 63  min = pCircle->c
1f50: 65 6e 74 65 72 79 20 2b 20 70 43 69 72 63 6c 65  entery + pCircle
1f60: 2d 3e 72 61 64 69 75 73 3b 0a 20 20 20 20 70 43  ->radius;.    pC
1f70: 69 72 63 6c 65 2d 3e 61 42 6f 78 5b 30 5d 2e 79  ircle->aBox[0].y
1f80: 6d 61 78 20 3d 20 70 43 69 72 63 6c 65 2d 3e 63  max = pCircle->c
1f90: 65 6e 74 65 72 79 20 2d 20 70 43 69 72 63 6c 65  entery - pCircle
1fa0: 2d 3e 72 61 64 69 75 73 3b 0a 20 20 20 20 70 43  ->radius;.    pC
1fb0: 69 72 63 6c 65 2d 3e 61 42 6f 78 5b 31 5d 2e 78  ircle->aBox[1].x
1fc0: 6d 69 6e 20 3d 20 70 43 69 72 63 6c 65 2d 3e 63  min = pCircle->c
1fd0: 65 6e 74 65 72 78 20 2b 20 70 43 69 72 63 6c 65  enterx + pCircle
1fe0: 2d 3e 72 61 64 69 75 73 3b 0a 20 20 20 20 70 43  ->radius;.    pC
1ff0: 69 72 63 6c 65 2d 3e 61 42 6f 78 5b 31 5d 2e 78  ircle->aBox[1].x
2000: 6d 61 78 20 3d 20 70 43 69 72 63 6c 65 2d 3e 63  max = pCircle->c
2010: 65 6e 74 65 72 78 20 2d 20 70 43 69 72 63 6c 65  enterx - pCircle
2020: 2d 3e 72 61 64 69 75 73 3b 0a 20 20 20 20 70 43  ->radius;.    pC
2030: 69 72 63 6c 65 2d 3e 61 42 6f 78 5b 31 5d 2e 79  ircle->aBox[1].y
2040: 6d 69 6e 20 3d 20 70 43 69 72 63 6c 65 2d 3e 63  min = pCircle->c
2050: 65 6e 74 65 72 79 3b 0a 20 20 20 20 70 43 69 72  entery;.    pCir
2060: 63 6c 65 2d 3e 61 42 6f 78 5b 31 5d 2e 79 6d 61  cle->aBox[1].yma
2070: 78 20 3d 20 70 43 69 72 63 6c 65 2d 3e 63 65 6e  x = pCircle->cen
2080: 74 65 72 79 3b 0a 20 20 20 20 70 43 69 72 63 6c  tery;.    pCircl
2090: 65 2d 3e 6d 78 41 72 65 61 20 3d 20 32 30 30 2e  e->mxArea = 200.
20a0: 30 2a 32 30 30 2e 30 3b 0a 20 20 7d 0a 0a 20 20  0*200.0;.  }..  
20b0: 2f 2a 20 43 68 65 63 6b 20 69 66 20 61 6e 79 20  /* Check if any 
20c0: 6f 66 20 74 68 65 20 34 20 63 6f 72 6e 65 72 73  of the 4 corners
20d0: 20 6f 66 20 74 68 65 20 62 6f 75 6e 64 69 6e 67   of the bounding
20e0: 2d 62 6f 78 20 62 65 69 6e 67 20 74 65 73 74 65  -box being teste
20f0: 64 20 6c 69 65 20 0a 20 20 2a 2a 20 69 6e 73 69  d lie .  ** insi
2100: 64 65 20 74 68 65 20 63 69 72 63 75 6c 61 72 20  de the circular 
2110: 72 65 67 69 6f 6e 2e 20 49 66 20 74 68 65 79 20  region. If they 
2120: 64 6f 2c 20 74 68 65 6e 20 74 68 65 20 62 6f 75  do, then the bou
2130: 6e 64 69 6e 67 2d 62 6f 78 20 64 6f 65 73 0a 20  nding-box does. 
2140: 20 2a 2a 20 69 6e 74 65 72 73 65 63 74 20 74 68   ** intersect th
2150: 65 20 72 65 67 69 6f 6e 20 6f 66 20 69 6e 74 65  e region of inte
2160: 72 65 73 74 2e 20 53 65 74 20 74 68 65 20 6f 75  rest. Set the ou
2170: 74 70 75 74 20 76 61 72 69 61 62 6c 65 20 74 6f  tput variable to
2180: 20 74 72 75 65 20 61 6e 64 0a 20 20 2a 2a 20 72   true and.  ** r
2190: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 20  eturn SQLITE_OK 
21a0: 69 6e 20 74 68 69 73 20 63 61 73 65 2e 20 2a 2f  in this case. */
21b0: 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 34 3b  .  for(i=0; i<4;
21c0: 20 69 2b 2b 29 7b 0a 20 20 20 20 64 6f 75 62 6c   i++){.    doubl
21d0: 65 20 78 20 3d 20 28 69 26 30 78 30 31 29 20 3f  e x = (i&0x01) ?
21e0: 20 78 6d 61 78 20 3a 20 78 6d 69 6e 3b 0a 20 20   xmax : xmin;.  
21f0: 20 20 64 6f 75 62 6c 65 20 79 20 3d 20 28 69 26    double y = (i&
2200: 30 78 30 32 29 20 3f 20 79 6d 61 78 20 3a 20 79  0x02) ? ymax : y
2210: 6d 69 6e 3b 0a 20 20 20 20 64 6f 75 62 6c 65 20  min;.    double 
2220: 64 32 3b 0a 20 20 20 20 0a 20 20 20 20 64 32 20  d2;.    .    d2 
2230: 20 3d 20 28 78 2d 70 43 69 72 63 6c 65 2d 3e 63   = (x-pCircle->c
2240: 65 6e 74 65 72 78 29 2a 28 78 2d 70 43 69 72 63  enterx)*(x-pCirc
2250: 6c 65 2d 3e 63 65 6e 74 65 72 78 29 3b 0a 20 20  le->centerx);.  
2260: 20 20 64 32 20 2b 3d 20 28 79 2d 70 43 69 72 63    d2 += (y-pCirc
2270: 6c 65 2d 3e 63 65 6e 74 65 72 79 29 2a 28 79 2d  le->centery)*(y-
2280: 70 43 69 72 63 6c 65 2d 3e 63 65 6e 74 65 72 79  pCircle->centery
2290: 29 3b 0a 20 20 20 20 69 66 28 20 64 32 3c 28 70  );.    if( d2<(p
22a0: 43 69 72 63 6c 65 2d 3e 72 61 64 69 75 73 2a 70  Circle->radius*p
22b0: 43 69 72 63 6c 65 2d 3e 72 61 64 69 75 73 29 20  Circle->radius) 
22c0: 29 20 6e 57 69 74 68 69 6e 2b 2b 3b 0a 20 20 7d  ) nWithin++;.  }
22d0: 0a 0a 20 20 2f 2a 20 43 68 65 63 6b 20 69 66 20  ..  /* Check if 
22e0: 74 68 65 20 62 6f 75 6e 64 69 6e 67 20 62 6f 78  the bounding box
22f0: 20 63 6f 76 65 72 73 20 61 6e 79 20 6f 74 68 65   covers any othe
2300: 72 20 70 61 72 74 20 6f 66 20 74 68 65 20 63 69  r part of the ci
2310: 72 63 75 6c 61 72 20 72 65 67 69 6f 6e 2e 0a 20  rcular region.. 
2320: 20 2a 2a 20 53 65 65 20 63 6f 6d 6d 65 6e 74 73   ** See comments
2330: 20 61 62 6f 76 65 20 66 6f 72 20 61 20 64 65 73   above for a des
2340: 63 72 69 70 74 69 6f 6e 20 6f 66 20 68 6f 77 20  cription of how 
2350: 74 68 69 73 20 74 65 73 74 20 77 6f 72 6b 73 2e  this test works.
2360: 20 49 66 20 69 74 20 64 6f 65 73 0a 20 20 2a 2a   If it does.  **
2370: 20 63 6f 76 65 72 20 70 61 72 74 20 6f 66 20 74   cover part of t
2380: 68 65 20 63 69 72 63 75 6c 61 72 20 72 65 67 69  he circular regi
2390: 6f 6e 2c 20 73 65 74 20 74 68 65 20 6f 75 74 70  on, set the outp
23a0: 75 74 20 76 61 72 69 61 62 6c 65 20 74 6f 20 74  ut variable to t
23b0: 72 75 65 0a 20 20 2a 2a 20 61 6e 64 20 72 65 74  rue.  ** and ret
23c0: 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 2e 20 2a  urn SQLITE_OK. *
23d0: 2f 0a 20 20 69 66 28 20 6e 57 69 74 68 69 6e 3d  /.  if( nWithin=
23e0: 3d 30 20 29 7b 0a 20 20 20 20 66 6f 72 28 69 3d  =0 ){.    for(i=
23f0: 30 3b 20 69 3c 32 3b 20 69 2b 2b 29 7b 0a 20 20  0; i<2; i++){.  
2400: 20 20 20 20 69 66 28 20 78 6d 69 6e 3c 3d 70 43      if( xmin<=pC
2410: 69 72 63 6c 65 2d 3e 61 42 6f 78 5b 69 5d 2e 78  ircle->aBox[i].x
2420: 6d 69 6e 20 0a 20 20 20 20 20 20 20 26 26 20 78  min .       && x
2430: 6d 61 78 3e 3d 70 43 69 72 63 6c 65 2d 3e 61 42  max>=pCircle->aB
2440: 6f 78 5b 69 5d 2e 78 6d 61 78 20 0a 20 20 20 20  ox[i].xmax .    
2450: 20 20 20 26 26 20 79 6d 69 6e 3c 3d 70 43 69 72     && ymin<=pCir
2460: 63 6c 65 2d 3e 61 42 6f 78 5b 69 5d 2e 79 6d 69  cle->aBox[i].ymi
2470: 6e 20 0a 20 20 20 20 20 20 20 26 26 20 79 6d 61  n .       && yma
2480: 78 3e 3d 70 43 69 72 63 6c 65 2d 3e 61 42 6f 78  x>=pCircle->aBox
2490: 5b 69 5d 2e 79 6d 61 78 20 0a 20 20 20 20 20 20  [i].ymax .      
24a0: 29 7b 0a 20 20 20 20 20 20 20 20 6e 57 69 74 68  ){.        nWith
24b0: 69 6e 20 3d 20 31 3b 0a 20 20 20 20 20 20 20 20  in = 1;.        
24c0: 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20  break;.      }. 
24d0: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 69 66 28 20     }.  }..  if( 
24e0: 70 43 69 72 63 6c 65 2d 3e 65 53 63 6f 72 65 54  pCircle->eScoreT
24f0: 79 70 65 3d 3d 31 20 29 7b 0a 20 20 20 20 2f 2a  ype==1 ){.    /*
2500: 20 44 65 70 74 68 20 66 69 72 73 74 20 73 65 61   Depth first sea
2510: 72 63 68 20 2a 2f 0a 20 20 20 20 70 2d 3e 72 53  rch */.    p->rS
2520: 63 6f 72 65 20 3d 20 70 2d 3e 69 4c 65 76 65 6c  core = p->iLevel
2530: 3b 0a 20 20 7d 65 6c 73 65 20 69 66 28 20 70 43  ;.  }else if( pC
2540: 69 72 63 6c 65 2d 3e 65 53 63 6f 72 65 54 79 70  ircle->eScoreTyp
2550: 65 3d 3d 32 20 29 7b 0a 20 20 20 20 2f 2a 20 42  e==2 ){.    /* B
2560: 72 65 61 64 74 68 20 66 69 72 73 74 20 73 65 61  readth first sea
2570: 72 63 68 20 2a 2f 0a 20 20 20 20 70 2d 3e 72 53  rch */.    p->rS
2580: 63 6f 72 65 20 3d 20 31 30 30 20 2d 20 70 2d 3e  core = 100 - p->
2590: 69 4c 65 76 65 6c 3b 0a 20 20 7d 65 6c 73 65 20  iLevel;.  }else 
25a0: 69 66 28 20 70 43 69 72 63 6c 65 2d 3e 65 53 63  if( pCircle->eSc
25b0: 6f 72 65 54 79 70 65 3d 3d 33 20 29 7b 0a 20 20  oreType==3 ){.  
25c0: 20 20 2f 2a 20 44 65 70 74 68 2d 66 69 72 73 74    /* Depth-first
25d0: 20 73 65 61 72 63 68 2c 20 65 78 63 65 70 74 20   search, except 
25e0: 73 6f 72 74 20 74 68 65 20 6c 65 61 66 20 6e 6f  sort the leaf no
25f0: 64 65 73 20 62 79 20 61 72 65 61 20 77 69 74 68  des by area with
2600: 0a 20 20 20 20 2a 2a 20 74 68 65 20 6c 61 72 67  .    ** the larg
2610: 65 73 74 20 61 72 65 61 20 66 69 72 73 74 20 2a  est area first *
2620: 2f 0a 20 20 20 20 69 66 28 20 70 2d 3e 69 4c 65  /.    if( p->iLe
2630: 76 65 6c 3d 3d 31 20 29 7b 0a 20 20 20 20 20 20  vel==1 ){.      
2640: 70 2d 3e 72 53 63 6f 72 65 20 3d 20 31 2e 30 20  p->rScore = 1.0 
2650: 2d 20 28 78 6d 61 78 2d 78 6d 69 6e 29 2a 28 79  - (xmax-xmin)*(y
2660: 6d 61 78 2d 79 6d 69 6e 29 2f 70 43 69 72 63 6c  max-ymin)/pCircl
2670: 65 2d 3e 6d 78 41 72 65 61 3b 0a 20 20 20 20 20  e->mxArea;.     
2680: 20 69 66 28 20 70 2d 3e 72 53 63 6f 72 65 3c 30   if( p->rScore<0
2690: 2e 30 31 20 29 20 70 2d 3e 72 53 63 6f 72 65 20  .01 ) p->rScore 
26a0: 3d 20 30 2e 30 31 3b 0a 20 20 20 20 7d 65 6c 73  = 0.01;.    }els
26b0: 65 7b 0a 20 20 20 20 20 20 70 2d 3e 72 53 63 6f  e{.      p->rSco
26c0: 72 65 20 3d 20 30 2e 30 3b 0a 20 20 20 20 7d 0a  re = 0.0;.    }.
26d0: 20 20 7d 65 6c 73 65 20 69 66 28 20 70 43 69 72    }else if( pCir
26e0: 63 6c 65 2d 3e 65 53 63 6f 72 65 54 79 70 65 3d  cle->eScoreType=
26f0: 3d 34 20 29 7b 0a 20 20 20 20 2f 2a 20 44 65 70  =4 ){.    /* Dep
2700: 74 68 2d 66 69 72 73 74 20 73 65 61 72 63 68 2c  th-first search,
2710: 20 65 78 63 65 70 74 20 65 78 63 6c 75 64 65 20   except exclude 
2720: 6f 64 64 20 72 6f 77 69 64 73 20 2a 2f 0a 20 20  odd rowids */.  
2730: 20 20 70 2d 3e 72 53 63 6f 72 65 20 3d 20 70 2d    p->rScore = p-
2740: 3e 69 4c 65 76 65 6c 3b 0a 20 20 20 20 69 66 28  >iLevel;.    if(
2750: 20 70 2d 3e 69 52 6f 77 69 64 26 31 20 29 20 6e   p->iRowid&1 ) n
2760: 57 69 74 68 69 6e 20 3d 20 30 3b 0a 20 20 7d 65  Within = 0;.  }e
2770: 6c 73 65 7b 0a 20 20 20 20 2f 2a 20 42 72 65 61  lse{.    /* Brea
2780: 64 74 68 2d 66 69 72 73 74 20 73 65 61 72 63 68  dth-first search
2790: 2c 20 65 78 63 65 70 74 20 65 78 63 6c 75 64 65  , except exclude
27a0: 20 6f 64 64 20 72 6f 77 69 64 73 20 2a 2f 0a 20   odd rowids */. 
27b0: 20 20 20 70 2d 3e 72 53 63 6f 72 65 20 3d 20 31     p->rScore = 1
27c0: 30 30 20 2d 20 70 2d 3e 69 4c 65 76 65 6c 3b 0a  00 - p->iLevel;.
27d0: 20 20 20 20 69 66 28 20 70 2d 3e 69 52 6f 77 69      if( p->iRowi
27e0: 64 26 31 20 29 20 6e 57 69 74 68 69 6e 20 3d 20  d&1 ) nWithin = 
27f0: 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20 6e 57 69  0;.  }.  if( nWi
2800: 74 68 69 6e 3d 3d 30 20 29 7b 0a 20 20 20 20 70  thin==0 ){.    p
2810: 2d 3e 65 57 69 74 68 69 6e 20 3d 20 4e 4f 54 5f  ->eWithin = NOT_
2820: 57 49 54 48 49 4e 3b 0a 20 20 7d 65 6c 73 65 20  WITHIN;.  }else 
2830: 69 66 28 20 6e 57 69 74 68 69 6e 3e 3d 34 20 29  if( nWithin>=4 )
2840: 7b 0a 20 20 20 20 70 2d 3e 65 57 69 74 68 69 6e  {.    p->eWithin
2850: 20 3d 20 46 55 4c 4c 59 5f 57 49 54 48 49 4e 3b   = FULLY_WITHIN;
2860: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 2d  .  }else{.    p-
2870: 3e 65 57 69 74 68 69 6e 20 3d 20 50 41 52 54 4c  >eWithin = PARTL
2880: 59 5f 57 49 54 48 49 4e 3b 0a 20 20 7d 0a 20 20  Y_WITHIN;.  }.  
2890: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
28a0: 3b 0a 7d 0a 2f 2a 0a 2a 2a 20 49 6d 70 6c 65 6d  ;.}./*.** Implem
28b0: 65 6e 74 61 74 69 6f 6e 20 6f 66 20 22 62 72 65  entation of "bre
28c0: 61 64 74 68 66 69 72 73 74 73 65 61 72 63 68 22  adthfirstsearch"
28d0: 20 72 2d 74 72 65 65 20 67 65 6f 6d 65 74 72 79   r-tree geometry
28e0: 20 63 61 6c 6c 62 61 63 6b 20 75 73 69 6e 67 20   callback using 
28f0: 74 68 65 20 0a 2a 2a 20 32 6e 64 2d 67 65 6e 65  the .** 2nd-gene
2900: 72 61 74 69 6f 6e 20 69 6e 74 65 72 66 61 63 65  ration interface
2910: 20 74 68 61 74 20 61 6c 6c 6f 77 73 20 73 63 6f   that allows sco
2920: 72 69 6e 67 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20  ring..**.**     
2930: 2e 2e 2e 20 57 48 45 52 45 20 69 64 20 4d 41 54  ... WHERE id MAT
2940: 43 48 20 62 72 65 61 64 74 68 66 69 72 73 74 73  CH breadthfirsts
2950: 65 61 72 63 68 28 24 78 30 2c 24 78 31 2c 24 79  earch($x0,$x1,$y
2960: 30 2c 24 79 31 29 20 2e 2e 2e 0a 2a 2a 0a 2a 2a  0,$y1) ....**.**
2970: 20 49 74 20 72 65 74 75 72 6e 73 20 61 6c 6c 20   It returns all 
2980: 65 6e 74 72 69 65 73 20 77 68 6f 73 65 20 62 6f  entries whose bo
2990: 75 6e 64 69 6e 67 20 62 6f 78 65 73 20 6f 76 65  unding boxes ove
29a0: 72 6c 61 70 20 77 69 74 68 20 24 78 30 2c 24 78  rlap with $x0,$x
29b0: 31 2c 24 79 30 2c 24 79 31 2e 0a 2a 2f 0a 73 74  1,$y0,$y1..*/.st
29c0: 61 74 69 63 20 69 6e 74 20 62 66 73 5f 71 75 65  atic int bfs_que
29d0: 72 79 5f 66 75 6e 63 28 73 71 6c 69 74 65 33 5f  ry_func(sqlite3_
29e0: 72 74 72 65 65 5f 71 75 65 72 79 5f 69 6e 66 6f  rtree_query_info
29f0: 20 2a 70 29 7b 0a 20 20 64 6f 75 62 6c 65 20 78   *p){.  double x
2a00: 30 2c 78 31 2c 79 30 2c 79 31 3b 20 20 20 20 20  0,x1,y0,y1;     
2a10: 20 20 20 2f 2a 20 44 69 6d 65 6e 73 69 6f 6e 73     /* Dimensions
2a20: 20 6f 66 20 62 6f 78 20 62 65 69 6e 67 20 74 65   of box being te
2a30: 73 74 65 64 20 2a 2f 0a 20 20 64 6f 75 62 6c 65  sted */.  double
2a40: 20 62 78 30 2c 62 78 31 2c 62 79 30 2c 62 79 31   bx0,bx1,by0,by1
2a50: 3b 20 20 20 20 2f 2a 20 42 6f 75 6e 64 61 72 79  ;    /* Boundary
2a60: 20 6f 66 20 74 68 65 20 71 75 65 72 79 20 66 75   of the query fu
2a70: 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69 66 28  nction */..  if(
2a80: 20 70 2d 3e 6e 50 61 72 61 6d 21 3d 34 20 29 20   p->nParam!=4 ) 
2a90: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 45 52  return SQLITE_ER
2aa0: 52 4f 52 3b 0a 20 20 78 30 20 3d 20 70 2d 3e 61  ROR;.  x0 = p->a
2ab0: 43 6f 6f 72 64 5b 30 5d 3b 0a 20 20 78 31 20 3d  Coord[0];.  x1 =
2ac0: 20 70 2d 3e 61 43 6f 6f 72 64 5b 31 5d 3b 0a 20   p->aCoord[1];. 
2ad0: 20 79 30 20 3d 20 70 2d 3e 61 43 6f 6f 72 64 5b   y0 = p->aCoord[
2ae0: 32 5d 3b 0a 20 20 79 31 20 3d 20 70 2d 3e 61 43  2];.  y1 = p->aC
2af0: 6f 6f 72 64 5b 33 5d 3b 0a 20 20 62 78 30 20 3d  oord[3];.  bx0 =
2b00: 20 70 2d 3e 61 50 61 72 61 6d 5b 30 5d 3b 0a 20   p->aParam[0];. 
2b10: 20 62 78 31 20 3d 20 70 2d 3e 61 50 61 72 61 6d   bx1 = p->aParam
2b20: 5b 31 5d 3b 0a 20 20 62 79 30 20 3d 20 70 2d 3e  [1];.  by0 = p->
2b30: 61 50 61 72 61 6d 5b 32 5d 3b 0a 20 20 62 79 31  aParam[2];.  by1
2b40: 20 3d 20 70 2d 3e 61 50 61 72 61 6d 5b 33 5d 3b   = p->aParam[3];
2b50: 0a 20 20 70 2d 3e 72 53 63 6f 72 65 20 3d 20 31  .  p->rScore = 1
2b60: 30 30 20 2d 20 70 2d 3e 69 4c 65 76 65 6c 3b 0a  00 - p->iLevel;.
2b70: 20 20 69 66 28 20 70 2d 3e 65 50 61 72 65 6e 74    if( p->eParent
2b80: 57 69 74 68 69 6e 3d 3d 46 55 4c 4c 59 5f 57 49  Within==FULLY_WI
2b90: 54 48 49 4e 20 29 7b 0a 20 20 20 20 70 2d 3e 65  THIN ){.    p->e
2ba0: 57 69 74 68 69 6e 20 3d 20 46 55 4c 4c 59 5f 57  Within = FULLY_W
2bb0: 49 54 48 49 4e 3b 0a 20 20 7d 65 6c 73 65 20 69  ITHIN;.  }else i
2bc0: 66 28 20 78 30 3e 3d 62 78 30 20 26 26 20 78 31  f( x0>=bx0 && x1
2bd0: 3c 3d 62 78 31 20 26 26 20 79 30 3e 3d 62 79 30  <=bx1 && y0>=by0
2be0: 20 26 26 20 79 31 3c 3d 62 79 31 20 29 7b 0a 20   && y1<=by1 ){. 
2bf0: 20 20 20 70 2d 3e 65 57 69 74 68 69 6e 20 3d 20     p->eWithin = 
2c00: 46 55 4c 4c 59 5f 57 49 54 48 49 4e 3b 0a 20 20  FULLY_WITHIN;.  
2c10: 7d 65 6c 73 65 20 69 66 28 20 78 31 3e 3d 62 78  }else if( x1>=bx
2c20: 30 20 26 26 20 78 30 3c 3d 62 78 31 20 26 26 20  0 && x0<=bx1 && 
2c30: 79 31 3e 3d 62 79 30 20 26 26 20 79 30 3c 3d 62  y1>=by0 && y0<=b
2c40: 79 31 20 29 7b 0a 20 20 20 20 70 2d 3e 65 57 69  y1 ){.    p->eWi
2c50: 74 68 69 6e 20 3d 20 50 41 52 54 4c 59 5f 57 49  thin = PARTLY_WI
2c60: 54 48 49 4e 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  THIN;.  }else{. 
2c70: 20 20 20 70 2d 3e 65 57 69 74 68 69 6e 20 3d 20     p->eWithin = 
2c80: 4e 4f 54 5f 57 49 54 48 49 4e 3b 0a 20 20 7d 0a  NOT_WITHIN;.  }.
2c90: 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f    return SQLITE_
2ca0: 4f 4b 3b 0a 7d 0a 0a 2f 2a 20 45 4e 44 20 6f 66  OK;.}../* END of
2cb0: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20   implementation 
2cc0: 6f 66 20 22 63 69 72 63 6c 65 22 20 67 65 6f 6d  of "circle" geom
2cd0: 65 74 72 79 20 63 61 6c 6c 62 61 63 6b 2e 0a 2a  etry callback..*
2ce0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2cf0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2d00: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2d10: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2d20: 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 2a 2a 2a 2a 2a 2a  *********.******
2d30: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2d40: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2d50: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2d60: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
2d70: 2a 2a 2a 2f 0a 0a 23 69 6e 63 6c 75 64 65 20 3c  ***/..#include <
2d80: 61 73 73 65 72 74 2e 68 3e 0a 23 69 6e 63 6c 75  assert.h>.#inclu
2d90: 64 65 20 22 74 63 6c 2e 68 22 0a 0a 74 79 70 65  de "tcl.h"..type
2da0: 64 65 66 20 73 74 72 75 63 74 20 43 75 62 65 20  def struct Cube 
2db0: 43 75 62 65 3b 0a 73 74 72 75 63 74 20 43 75 62  Cube;.struct Cub
2dc0: 65 20 7b 0a 20 20 64 6f 75 62 6c 65 20 78 3b 0a  e {.  double x;.
2dd0: 20 20 64 6f 75 62 6c 65 20 79 3b 0a 20 20 64 6f    double y;.  do
2de0: 75 62 6c 65 20 7a 3b 0a 20 20 64 6f 75 62 6c 65  uble z;.  double
2df0: 20 77 69 64 74 68 3b 0a 20 20 64 6f 75 62 6c 65   width;.  double
2e00: 20 68 65 69 67 68 74 3b 0a 20 20 64 6f 75 62 6c   height;.  doubl
2e10: 65 20 64 65 70 74 68 3b 0a 7d 3b 0a 0a 73 74 61  e depth;.};..sta
2e20: 74 69 63 20 76 6f 69 64 20 63 75 62 65 5f 63 6f  tic void cube_co
2e30: 6e 74 65 78 74 5f 66 72 65 65 28 76 6f 69 64 20  ntext_free(void 
2e40: 2a 70 29 7b 0a 20 20 73 71 6c 69 74 65 33 5f 66  *p){.  sqlite3_f
2e50: 72 65 65 28 70 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  ree(p);.}../*.**
2e60: 20 54 68 65 20 63 6f 6e 74 65 78 74 20 70 6f 69   The context poi
2e70: 6e 74 65 72 20 72 65 67 69 73 74 65 72 65 64 20  nter registered 
2e80: 61 6c 6f 6e 67 20 77 69 74 68 20 74 68 65 20 27  along with the '
2e90: 63 75 62 65 27 20 63 61 6c 6c 62 61 63 6b 20 69  cube' callback i
2ea0: 73 0a 2a 2a 20 61 6c 77 61 79 73 20 28 28 76 6f  s.** always ((vo
2eb0: 69 64 20 2a 29 26 67 48 65 72 65 29 2e 20 54 68  id *)&gHere). Th
2ec0: 69 73 20 69 73 20 6a 75 73 74 20 74 6f 20 66 61  is is just to fa
2ed0: 63 69 6c 69 74 61 74 65 20 74 65 73 74 69 6e 67  cilitate testing
2ee0: 2c 20 69 74 20 69 73 20 6e 6f 74 0a 2a 2a 20 61  , it is not.** a
2ef0: 63 74 75 61 6c 6c 79 20 75 73 65 64 20 66 6f 72  ctually used for
2f00: 20 61 6e 79 74 68 69 6e 67 2e 0a 2a 2f 0a 73 74   anything..*/.st
2f10: 61 74 69 63 20 69 6e 74 20 67 48 65 72 65 20 3d  atic int gHere =
2f20: 20 34 32 3b 0a 0a 2f 2a 0a 2a 2a 20 49 6d 70 6c   42;../*.** Impl
2f30: 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 61 20  ementation of a 
2f40: 73 69 6d 70 6c 65 20 72 2d 74 72 65 65 20 67 65  simple r-tree ge
2f50: 6f 6d 20 63 61 6c 6c 62 61 63 6b 20 74 6f 20 74  om callback to t
2f60: 65 73 74 20 66 6f 72 20 69 6e 74 65 72 73 65 63  est for intersec
2f70: 74 69 6f 6e 0a 2a 2a 20 6f 66 20 72 2d 74 72 65  tion.** of r-tre
2f80: 65 20 72 6f 77 73 20 77 69 74 68 20 61 20 22 63  e rows with a "c
2f90: 75 62 65 22 20 73 68 61 70 65 2e 20 43 75 62 65  ube" shape. Cube
2fa0: 73 20 61 72 65 20 64 65 66 69 6e 65 64 20 62 79  s are defined by
2fb0: 20 73 69 78 20 73 63 61 6c 61 72 0a 2a 2a 20 63   six scalar.** c
2fc0: 6f 6f 72 64 69 6e 61 74 65 73 20 61 73 20 66 6f  oordinates as fo
2fd0: 6c 6c 6f 77 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 63  llows:.**.**   c
2fe0: 75 62 65 28 78 2c 20 79 2c 20 7a 2c 20 77 69 64  ube(x, y, z, wid
2ff0: 74 68 2c 20 68 65 69 67 68 74 2c 20 64 65 70 74  th, height, dept
3000: 68 29 0a 2a 2a 0a 2a 2a 20 54 68 65 20 77 69 64  h).**.** The wid
3010: 74 68 2c 20 68 65 69 67 68 74 20 61 6e 64 20 64  th, height and d
3020: 65 70 74 68 20 70 61 72 61 6d 65 74 65 72 73 20  epth parameters 
3030: 6d 75 73 74 20 61 6c 6c 20 62 65 20 67 72 65 61  must all be grea
3040: 74 65 72 20 74 68 61 6e 20 7a 65 72 6f 2e 0a 2a  ter than zero..*
3050: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 63 75 62  /.static int cub
3060: 65 5f 67 65 6f 6d 28 0a 20 20 73 71 6c 69 74 65  e_geom(.  sqlite
3070: 33 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79  3_rtree_geometry
3080: 20 2a 70 2c 0a 20 20 69 6e 74 20 6e 43 6f 6f 72   *p,.  int nCoor
3090: 64 2c 0a 20 20 73 71 6c 69 74 65 33 5f 72 74 72  d,.  sqlite3_rtr
30a0: 65 65 5f 64 62 6c 20 2a 61 43 6f 6f 72 64 2c 0a  ee_dbl *aCoord,.
30b0: 20 20 69 6e 74 20 2a 70 69 52 65 73 0a 29 7b 0a    int *piRes.){.
30c0: 20 20 43 75 62 65 20 2a 70 43 75 62 65 20 3d 20    Cube *pCube = 
30d0: 28 43 75 62 65 20 2a 29 70 2d 3e 70 55 73 65 72  (Cube *)p->pUser
30e0: 3b 0a 0a 20 20 61 73 73 65 72 74 28 20 70 2d 3e  ;..  assert( p->
30f0: 70 43 6f 6e 74 65 78 74 3d 3d 28 76 6f 69 64 20  pContext==(void 
3100: 2a 29 26 67 48 65 72 65 20 29 3b 0a 0a 20 20 69  *)&gHere );..  i
3110: 66 28 20 70 43 75 62 65 3d 3d 30 20 29 7b 0a 20  f( pCube==0 ){. 
3120: 20 20 20 69 66 28 20 70 2d 3e 6e 50 61 72 61 6d     if( p->nParam
3130: 21 3d 36 20 7c 7c 20 6e 43 6f 6f 72 64 21 3d 36  !=6 || nCoord!=6
3140: 0a 20 20 20 20 20 7c 7c 20 70 2d 3e 61 50 61 72  .     || p->aPar
3150: 61 6d 5b 33 5d 3c 3d 30 2e 30 20 7c 7c 20 70 2d  am[3]<=0.0 || p-
3160: 3e 61 50 61 72 61 6d 5b 34 5d 3c 3d 30 2e 30 20  >aParam[4]<=0.0 
3170: 7c 7c 20 70 2d 3e 61 50 61 72 61 6d 5b 35 5d 3c  || p->aParam[5]<
3180: 3d 30 2e 30 0a 20 20 20 20 29 7b 0a 20 20 20 20  =0.0.    ){.    
3190: 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f    return SQLITE_
31a0: 45 52 52 4f 52 3b 0a 20 20 20 20 7d 0a 20 20 20  ERROR;.    }.   
31b0: 20 70 43 75 62 65 20 3d 20 28 43 75 62 65 20 2a   pCube = (Cube *
31c0: 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28  )sqlite3_malloc(
31d0: 73 69 7a 65 6f 66 28 43 75 62 65 29 29 3b 0a 20  sizeof(Cube));. 
31e0: 20 20 20 69 66 28 20 21 70 43 75 62 65 20 29 7b     if( !pCube ){
31f0: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 53 51  .      return SQ
3200: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20  LITE_NOMEM;.    
3210: 7d 0a 20 20 20 20 70 43 75 62 65 2d 3e 78 20 3d  }.    pCube->x =
3220: 20 70 2d 3e 61 50 61 72 61 6d 5b 30 5d 3b 0a 20   p->aParam[0];. 
3230: 20 20 20 70 43 75 62 65 2d 3e 79 20 3d 20 70 2d     pCube->y = p-
3240: 3e 61 50 61 72 61 6d 5b 31 5d 3b 0a 20 20 20 20  >aParam[1];.    
3250: 70 43 75 62 65 2d 3e 7a 20 3d 20 70 2d 3e 61 50  pCube->z = p->aP
3260: 61 72 61 6d 5b 32 5d 3b 0a 20 20 20 20 70 43 75  aram[2];.    pCu
3270: 62 65 2d 3e 77 69 64 74 68 20 3d 20 70 2d 3e 61  be->width = p->a
3280: 50 61 72 61 6d 5b 33 5d 3b 0a 20 20 20 20 70 43  Param[3];.    pC
3290: 75 62 65 2d 3e 68 65 69 67 68 74 20 3d 20 70 2d  ube->height = p-
32a0: 3e 61 50 61 72 61 6d 5b 34 5d 3b 0a 20 20 20 20  >aParam[4];.    
32b0: 70 43 75 62 65 2d 3e 64 65 70 74 68 20 3d 20 70  pCube->depth = p
32c0: 2d 3e 61 50 61 72 61 6d 5b 35 5d 3b 0a 0a 20 20  ->aParam[5];..  
32d0: 20 20 70 2d 3e 70 55 73 65 72 20 3d 20 28 76 6f    p->pUser = (vo
32e0: 69 64 20 2a 29 70 43 75 62 65 3b 0a 20 20 20 20  id *)pCube;.    
32f0: 70 2d 3e 78 44 65 6c 55 73 65 72 20 3d 20 63 75  p->xDelUser = cu
3300: 62 65 5f 63 6f 6e 74 65 78 74 5f 66 72 65 65 3b  be_context_free;
3310: 0a 20 20 7d 0a 0a 20 20 61 73 73 65 72 74 28 20  .  }..  assert( 
3320: 6e 43 6f 6f 72 64 3d 3d 36 20 29 3b 0a 20 20 2a  nCoord==6 );.  *
3330: 70 69 52 65 73 20 3d 20 30 3b 0a 20 20 69 66 28  piRes = 0;.  if(
3340: 20 61 43 6f 6f 72 64 5b 30 5d 3c 3d 28 70 43 75   aCoord[0]<=(pCu
3350: 62 65 2d 3e 78 2b 70 43 75 62 65 2d 3e 77 69 64  be->x+pCube->wid
3360: 74 68 29 0a 20 20 20 26 26 20 61 43 6f 6f 72 64  th).   && aCoord
3370: 5b 31 5d 3e 3d 70 43 75 62 65 2d 3e 78 0a 20 20  [1]>=pCube->x.  
3380: 20 26 26 20 61 43 6f 6f 72 64 5b 32 5d 3c 3d 28   && aCoord[2]<=(
3390: 70 43 75 62 65 2d 3e 79 2b 70 43 75 62 65 2d 3e  pCube->y+pCube->
33a0: 68 65 69 67 68 74 29 0a 20 20 20 26 26 20 61 43  height).   && aC
33b0: 6f 6f 72 64 5b 33 5d 3e 3d 70 43 75 62 65 2d 3e  oord[3]>=pCube->
33c0: 79 0a 20 20 20 26 26 20 61 43 6f 6f 72 64 5b 34  y.   && aCoord[4
33d0: 5d 3c 3d 28 70 43 75 62 65 2d 3e 7a 2b 70 43 75  ]<=(pCube->z+pCu
33e0: 62 65 2d 3e 64 65 70 74 68 29 0a 20 20 20 26 26  be->depth).   &&
33f0: 20 61 43 6f 6f 72 64 5b 35 5d 3e 3d 70 43 75 62   aCoord[5]>=pCub
3400: 65 2d 3e 7a 0a 20 20 29 7b 0a 20 20 20 20 2a 70  e->z.  ){.    *p
3410: 69 52 65 73 20 3d 20 31 3b 0a 20 20 7d 0a 0a 20  iRes = 1;.  }.. 
3420: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f   return SQLITE_O
3430: 4b 3b 0a 7d 0a 23 65 6e 64 69 66 20 2f 2a 20 53  K;.}.#endif /* S
3440: 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 52 54 52  QLITE_ENABLE_RTR
3450: 45 45 20 2a 2f 0a 0a 73 74 61 74 69 63 20 69 6e  EE */..static in
3460: 74 20 72 65 67 69 73 74 65 72 5f 63 75 62 65 5f  t register_cube_
3470: 67 65 6f 6d 28 0a 20 20 76 6f 69 64 20 2a 20 63  geom(.  void * c
3480: 6c 69 65 6e 74 44 61 74 61 2c 0a 20 20 54 63 6c  lientData,.  Tcl
3490: 5f 49 6e 74 65 72 70 20 2a 69 6e 74 65 72 70 2c  _Interp *interp,
34a0: 0a 20 20 69 6e 74 20 6f 62 6a 63 2c 0a 20 20 54  .  int objc,.  T
34b0: 63 6c 5f 4f 62 6a 20 2a 43 4f 4e 53 54 20 6f 62  cl_Obj *CONST ob
34c0: 6a 76 5b 5d 0a 29 7b 0a 23 69 66 6e 64 65 66 20  jv[].){.#ifndef 
34d0: 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 52 54  SQLITE_ENABLE_RT
34e0: 52 45 45 0a 20 20 55 4e 55 53 45 44 5f 50 41 52  REE.  UNUSED_PAR
34f0: 41 4d 45 54 45 52 28 63 6c 69 65 6e 74 44 61 74  AMETER(clientDat
3500: 61 29 3b 0a 20 20 55 4e 55 53 45 44 5f 50 41 52  a);.  UNUSED_PAR
3510: 41 4d 45 54 45 52 28 69 6e 74 65 72 70 29 3b 0a  AMETER(interp);.
3520: 20 20 55 4e 55 53 45 44 5f 50 41 52 41 4d 45 54    UNUSED_PARAMET
3530: 45 52 28 6f 62 6a 63 29 3b 0a 20 20 55 4e 55 53  ER(objc);.  UNUS
3540: 45 44 5f 50 41 52 41 4d 45 54 45 52 28 6f 62 6a  ED_PARAMETER(obj
3550: 76 29 3b 0a 23 65 6c 73 65 0a 20 20 65 78 74 65  v);.#else.  exte
3560: 72 6e 20 69 6e 74 20 67 65 74 44 62 50 6f 69 6e  rn int getDbPoin
3570: 74 65 72 28 54 63 6c 5f 49 6e 74 65 72 70 2a 2c  ter(Tcl_Interp*,
3580: 20 63 6f 6e 73 74 20 63 68 61 72 2a 2c 20 73 71   const char*, sq
3590: 6c 69 74 65 33 2a 2a 29 3b 0a 20 20 65 78 74 65  lite3**);.  exte
35a0: 72 6e 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 73  rn const char *s
35b0: 71 6c 69 74 65 33 45 72 72 4e 61 6d 65 28 69 6e  qlite3ErrName(in
35c0: 74 29 3b 0a 20 20 73 71 6c 69 74 65 33 20 2a 64  t);.  sqlite3 *d
35d0: 62 3b 0a 20 20 69 6e 74 20 72 63 3b 0a 0a 20 20  b;.  int rc;..  
35e0: 69 66 28 20 6f 62 6a 63 21 3d 32 20 29 7b 0a 20  if( objc!=2 ){. 
35f0: 20 20 20 54 63 6c 5f 57 72 6f 6e 67 4e 75 6d 41     Tcl_WrongNumA
3600: 72 67 73 28 69 6e 74 65 72 70 2c 20 31 2c 20 6f  rgs(interp, 1, o
3610: 62 6a 76 2c 20 22 44 42 22 29 3b 0a 20 20 20 20  bjv, "DB");.    
3620: 72 65 74 75 72 6e 20 54 43 4c 5f 45 52 52 4f 52  return TCL_ERROR
3630: 3b 0a 20 20 7d 0a 20 20 69 66 28 20 67 65 74 44  ;.  }.  if( getD
3640: 62 50 6f 69 6e 74 65 72 28 69 6e 74 65 72 70 2c  bPointer(interp,
3650: 20 54 63 6c 5f 47 65 74 53 74 72 69 6e 67 28 6f   Tcl_GetString(o
3660: 62 6a 76 5b 31 5d 29 2c 20 26 64 62 29 20 29 20  bjv[1]), &db) ) 
3670: 72 65 74 75 72 6e 20 54 43 4c 5f 45 52 52 4f 52  return TCL_ERROR
3680: 3b 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33  ;.  rc = sqlite3
3690: 5f 72 74 72 65 65 5f 67 65 6f 6d 65 74 72 79 5f  _rtree_geometry_
36a0: 63 61 6c 6c 62 61 63 6b 28 64 62 2c 20 22 63 75  callback(db, "cu
36b0: 62 65 22 2c 20 63 75 62 65 5f 67 65 6f 6d 2c 20  be", cube_geom, 
36c0: 28 76 6f 69 64 20 2a 29 26 67 48 65 72 65 29 3b  (void *)&gHere);
36d0: 0a 20 20 54 63 6c 5f 53 65 74 52 65 73 75 6c 74  .  Tcl_SetResult
36e0: 28 69 6e 74 65 72 70 2c 20 28 63 68 61 72 20 2a  (interp, (char *
36f0: 29 73 71 6c 69 74 65 33 45 72 72 4e 61 6d 65 28  )sqlite3ErrName(
3700: 72 63 29 2c 20 54 43 4c 5f 53 54 41 54 49 43 29  rc), TCL_STATIC)
3710: 3b 0a 23 65 6e 64 69 66 0a 20 20 72 65 74 75 72  ;.#endif.  retur
3720: 6e 20 54 43 4c 5f 4f 4b 3b 0a 7d 0a 0a 73 74 61  n TCL_OK;.}..sta
3730: 74 69 63 20 69 6e 74 20 72 65 67 69 73 74 65 72  tic int register
3740: 5f 63 69 72 63 6c 65 5f 67 65 6f 6d 28 0a 20 20  _circle_geom(.  
3750: 76 6f 69 64 20 2a 20 63 6c 69 65 6e 74 44 61 74  void * clientDat
3760: 61 2c 0a 20 20 54 63 6c 5f 49 6e 74 65 72 70 20  a,.  Tcl_Interp 
3770: 2a 69 6e 74 65 72 70 2c 0a 20 20 69 6e 74 20 6f  *interp,.  int o
3780: 62 6a 63 2c 0a 20 20 54 63 6c 5f 4f 62 6a 20 2a  bjc,.  Tcl_Obj *
3790: 43 4f 4e 53 54 20 6f 62 6a 76 5b 5d 0a 29 7b 0a  CONST objv[].){.
37a0: 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 45  #ifndef SQLITE_E
37b0: 4e 41 42 4c 45 5f 52 54 52 45 45 0a 20 20 55 4e  NABLE_RTREE.  UN
37c0: 55 53 45 44 5f 50 41 52 41 4d 45 54 45 52 28 63  USED_PARAMETER(c
37d0: 6c 69 65 6e 74 44 61 74 61 29 3b 0a 20 20 55 4e  lientData);.  UN
37e0: 55 53 45 44 5f 50 41 52 41 4d 45 54 45 52 28 69  USED_PARAMETER(i
37f0: 6e 74 65 72 70 29 3b 0a 20 20 55 4e 55 53 45 44  nterp);.  UNUSED
3800: 5f 50 41 52 41 4d 45 54 45 52 28 6f 62 6a 63 29  _PARAMETER(objc)
3810: 3b 0a 20 20 55 4e 55 53 45 44 5f 50 41 52 41 4d  ;.  UNUSED_PARAM
3820: 45 54 45 52 28 6f 62 6a 76 29 3b 0a 23 65 6c 73  ETER(objv);.#els
3830: 65 0a 20 20 65 78 74 65 72 6e 20 69 6e 74 20 67  e.  extern int g
3840: 65 74 44 62 50 6f 69 6e 74 65 72 28 54 63 6c 5f  etDbPointer(Tcl_
3850: 49 6e 74 65 72 70 2a 2c 20 63 6f 6e 73 74 20 63  Interp*, const c
3860: 68 61 72 2a 2c 20 73 71 6c 69 74 65 33 2a 2a 29  har*, sqlite3**)
3870: 3b 0a 20 20 65 78 74 65 72 6e 20 63 6f 6e 73 74  ;.  extern const
3880: 20 63 68 61 72 20 2a 73 71 6c 69 74 65 33 45 72   char *sqlite3Er
3890: 72 4e 61 6d 65 28 69 6e 74 29 3b 0a 20 20 73 71  rName(int);.  sq
38a0: 6c 69 74 65 33 20 2a 64 62 3b 0a 20 20 69 6e 74  lite3 *db;.  int
38b0: 20 72 63 3b 0a 0a 20 20 69 66 28 20 6f 62 6a 63   rc;..  if( objc
38c0: 21 3d 32 20 29 7b 0a 20 20 20 20 54 63 6c 5f 57  !=2 ){.    Tcl_W
38d0: 72 6f 6e 67 4e 75 6d 41 72 67 73 28 69 6e 74 65  rongNumArgs(inte
38e0: 72 70 2c 20 31 2c 20 6f 62 6a 76 2c 20 22 44 42  rp, 1, objv, "DB
38f0: 22 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 54  ");.    return T
3900: 43 4c 5f 45 52 52 4f 52 3b 0a 20 20 7d 0a 20 20  CL_ERROR;.  }.  
3910: 69 66 28 20 67 65 74 44 62 50 6f 69 6e 74 65 72  if( getDbPointer
3920: 28 69 6e 74 65 72 70 2c 20 54 63 6c 5f 47 65 74  (interp, Tcl_Get
3930: 53 74 72 69 6e 67 28 6f 62 6a 76 5b 31 5d 29 2c  String(objv[1]),
3940: 20 26 64 62 29 20 29 20 72 65 74 75 72 6e 20 54   &db) ) return T
3950: 43 4c 5f 45 52 52 4f 52 3b 0a 20 20 72 63 20 3d  CL_ERROR;.  rc =
3960: 20 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 67   sqlite3_rtree_g
3970: 65 6f 6d 65 74 72 79 5f 63 61 6c 6c 62 61 63 6b  eometry_callback
3980: 28 64 62 2c 20 22 63 69 72 63 6c 65 22 2c 20 63  (db, "circle", c
3990: 69 72 63 6c 65 5f 67 65 6f 6d 2c 20 30 29 3b 0a  ircle_geom, 0);.
39a0: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45    if( rc==SQLITE
39b0: 5f 4f 4b 20 29 7b 0a 20 20 20 20 72 63 20 3d 20  _OK ){.    rc = 
39c0: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75  sqlite3_rtree_qu
39d0: 65 72 79 5f 63 61 6c 6c 62 61 63 6b 28 64 62 2c  ery_callback(db,
39e0: 20 22 51 63 69 72 63 6c 65 22 2c 0a 20 20 20 20   "Qcircle",.    
39f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3a00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3a10: 20 20 63 69 72 63 6c 65 5f 71 75 65 72 79 5f 66    circle_query_f
3a20: 75 6e 63 2c 20 30 2c 20 30 29 3b 0a 20 20 7d 0a  unc, 0, 0);.  }.
3a30: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45    if( rc==SQLITE
3a40: 5f 4f 4b 20 29 7b 0a 20 20 20 20 72 63 20 3d 20  _OK ){.    rc = 
3a50: 73 71 6c 69 74 65 33 5f 72 74 72 65 65 5f 71 75  sqlite3_rtree_qu
3a60: 65 72 79 5f 63 61 6c 6c 62 61 63 6b 28 64 62 2c  ery_callback(db,
3a70: 20 22 62 72 65 61 64 74 68 66 69 72 73 74 73 65   "breadthfirstse
3a80: 61 72 63 68 22 2c 0a 20 20 20 20 20 20 20 20 20  arch",.         
3a90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3aa0: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 66 73               bfs
3ab0: 5f 71 75 65 72 79 5f 66 75 6e 63 2c 20 30 2c 20  _query_func, 0, 
3ac0: 30 29 3b 0a 20 20 7d 0a 20 20 54 63 6c 5f 53 65  0);.  }.  Tcl_Se
3ad0: 74 52 65 73 75 6c 74 28 69 6e 74 65 72 70 2c 20  tResult(interp, 
3ae0: 28 63 68 61 72 20 2a 29 73 71 6c 69 74 65 33 45  (char *)sqlite3E
3af0: 72 72 4e 61 6d 65 28 72 63 29 2c 20 54 43 4c 5f  rrName(rc), TCL_
3b00: 53 54 41 54 49 43 29 3b 0a 23 65 6e 64 69 66 0a  STATIC);.#endif.
3b10: 20 20 72 65 74 75 72 6e 20 54 43 4c 5f 4f 4b 3b    return TCL_OK;
3b20: 0a 7d 0a 0a 69 6e 74 20 53 71 6c 69 74 65 74 65  .}..int Sqlitete
3b30: 73 74 72 74 72 65 65 5f 49 6e 69 74 28 54 63 6c  strtree_Init(Tcl
3b40: 5f 49 6e 74 65 72 70 20 2a 69 6e 74 65 72 70 29  _Interp *interp)
3b50: 7b 0a 20 20 54 63 6c 5f 43 72 65 61 74 65 4f 62  {.  Tcl_CreateOb
3b60: 6a 43 6f 6d 6d 61 6e 64 28 69 6e 74 65 72 70 2c  jCommand(interp,
3b70: 20 22 72 65 67 69 73 74 65 72 5f 63 75 62 65 5f   "register_cube_
3b80: 67 65 6f 6d 22 2c 20 72 65 67 69 73 74 65 72 5f  geom", register_
3b90: 63 75 62 65 5f 67 65 6f 6d 2c 20 30 2c 20 30 29  cube_geom, 0, 0)
3ba0: 3b 0a 20 20 54 63 6c 5f 43 72 65 61 74 65 4f 62  ;.  Tcl_CreateOb
3bb0: 6a 43 6f 6d 6d 61 6e 64 28 69 6e 74 65 72 70 2c  jCommand(interp,
3bc0: 20 22 72 65 67 69 73 74 65 72 5f 63 69 72 63 6c   "register_circl
3bd0: 65 5f 67 65 6f 6d 22 2c 72 65 67 69 73 74 65 72  e_geom",register
3be0: 5f 63 69 72 63 6c 65 5f 67 65 6f 6d 2c 30 2c 30  _circle_geom,0,0
3bf0: 29 3b 0a 20 20 72 65 74 75 72 6e 20 54 43 4c 5f  );.  return TCL_
3c00: 4f 4b 3b 0a 7d 0a                                OK;.}.