/ Hex Artifact Content
Login

Artifact 388c1c8602c3ce55c15f03b509e9cf545fb7c41f:


0000: 23 20 32 30 31 30 20 41 75 67 75 73 74 20 32 38  # 2010 August 28
0010: 0a 23 0a 23 20 54 68 65 20 61 75 74 68 6f 72 20  .#.# The author 
0020: 64 69 73 63 6c 61 69 6d 73 20 63 6f 70 79 72 69  disclaims copyri
0030: 67 68 74 20 74 6f 20 74 68 69 73 20 73 6f 75 72  ght to this sour
0040: 63 65 20 63 6f 64 65 2e 20 20 49 6e 20 70 6c 61  ce code.  In pla
0050: 63 65 20 6f 66 0a 23 20 61 20 6c 65 67 61 6c 20  ce of.# a legal 
0060: 6e 6f 74 69 63 65 2c 20 68 65 72 65 20 69 73 20  notice, here is 
0070: 61 20 62 6c 65 73 73 69 6e 67 3a 0a 23 0a 23 20  a blessing:.#.# 
0080: 20 20 20 4d 61 79 20 79 6f 75 20 64 6f 20 67 6f     May you do go
0090: 6f 64 20 61 6e 64 20 6e 6f 74 20 65 76 69 6c 2e  od and not evil.
00a0: 0a 23 20 20 20 20 4d 61 79 20 79 6f 75 20 66 69  .#    May you fi
00b0: 6e 64 20 66 6f 72 67 69 76 65 6e 65 73 73 20 66  nd forgiveness f
00c0: 6f 72 20 79 6f 75 72 73 65 6c 66 20 61 6e 64 20  or yourself and 
00d0: 66 6f 72 67 69 76 65 20 6f 74 68 65 72 73 2e 0a  forgive others..
00e0: 23 20 20 20 20 4d 61 79 20 79 6f 75 20 73 68 61  #    May you sha
00f0: 72 65 20 66 72 65 65 6c 79 2c 20 6e 65 76 65 72  re freely, never
0100: 20 74 61 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61   taking more tha
0110: 6e 20 79 6f 75 20 67 69 76 65 2e 0a 23 0a 23 2a  n you give..#.#*
0120: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
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 0a 23 20 54 68 69 73 20 66 69  ******.# This fi
0170: 6c 65 20 63 6f 6e 74 61 69 6e 73 20 74 65 73 74  le contains test
0180: 73 20 66 6f 72 20 74 68 65 20 72 2d 74 72 65 65  s for the r-tree
0190: 20 6d 6f 64 75 6c 65 2e 20 53 70 65 63 69 66 69   module. Specifi
01a0: 63 61 6c 6c 79 2c 20 69 74 20 74 65 73 74 73 0a  cally, it tests.
01b0: 23 20 74 68 61 74 20 6e 65 77 2d 73 74 79 6c 65  # that new-style
01c0: 20 63 75 73 74 6f 6d 20 72 2d 74 72 65 65 20 71   custom r-tree q
01d0: 75 65 72 69 65 73 20 28 67 65 6f 6d 65 74 72 79  ueries (geometry
01e0: 20 63 61 6c 6c 62 61 63 6b 73 29 20 77 6f 72 6b   callbacks) work
01f0: 2e 0a 23 20 0a 0a 69 66 20 7b 21 5b 69 6e 66 6f  ..# ..if {![info
0200: 20 65 78 69 73 74 73 20 74 65 73 74 64 69 72 5d   exists testdir]
0210: 7d 20 7b 0a 20 20 73 65 74 20 74 65 73 74 64 69  } {.  set testdi
0220: 72 20 5b 66 69 6c 65 20 6a 6f 69 6e 20 5b 66 69  r [file join [fi
0230: 6c 65 20 64 69 72 6e 61 6d 65 20 5b 69 6e 66 6f  le dirname [info
0240: 20 73 63 72 69 70 74 5d 5d 20 2e 2e 20 2e 2e 20   script]] .. .. 
0250: 74 65 73 74 5d 0a 7d 20 0a 73 6f 75 72 63 65 20  test].} .source 
0260: 24 74 65 73 74 64 69 72 2f 74 65 73 74 65 72 2e  $testdir/tester.
0270: 74 63 6c 0a 69 66 63 61 70 61 62 6c 65 20 21 72  tcl.ifcapable !r
0280: 74 72 65 65 20 7b 20 66 69 6e 69 73 68 5f 74 65  tree { finish_te
0290: 73 74 20 3b 20 72 65 74 75 72 6e 20 7d 0a 69 66  st ; return }.if
02a0: 63 61 70 61 62 6c 65 20 72 74 72 65 65 5f 69 6e  capable rtree_in
02b0: 74 5f 6f 6e 6c 79 20 7b 20 66 69 6e 69 73 68 5f  t_only { finish_
02c0: 74 65 73 74 3b 20 72 65 74 75 72 6e 20 7d 0a 0a  test; return }..
02d0: 0a 23 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  .#--------------
02e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
02f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0300: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0310: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 23 20 54 65  -----------.# Te
0320: 73 74 20 74 68 65 20 65 78 61 6d 70 6c 65 20 32  st the example 2
0330: 64 20 22 63 69 72 63 6c 65 22 20 67 65 6f 6d 65  d "circle" geome
0340: 74 72 79 20 63 61 6c 6c 62 61 63 6b 2e 0a 23 0a  try callback..#.
0350: 72 65 67 69 73 74 65 72 5f 63 69 72 63 6c 65 5f  register_circle_
0360: 67 65 6f 6d 20 64 62 0a 0a 64 6f 5f 65 78 65 63  geom db..do_exec
0370: 73 71 6c 5f 74 65 73 74 20 72 74 72 65 65 45 2d  sql_test rtreeE-
0380: 31 2e 31 20 7b 0a 20 20 50 52 41 47 4d 41 20 70  1.1 {.  PRAGMA p
0390: 61 67 65 5f 73 69 7a 65 3d 35 31 32 3b 0a 20 20  age_size=512;.  
03a0: 43 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54  CREATE VIRTUAL T
03b0: 41 42 4c 45 20 72 74 31 20 55 53 49 4e 47 20 72  ABLE rt1 USING r
03c0: 74 72 65 65 28 69 64 2c 78 30 2c 78 31 2c 79 30  tree(id,x0,x1,y0
03d0: 2c 79 31 29 3b 0a 20 20 0a 20 20 2f 2a 20 41 20  ,y1);.  .  /* A 
03e0: 74 69 67 68 74 20 70 61 74 74 65 72 6e 20 6f 66  tight pattern of
03f0: 20 73 6d 61 6c 6c 20 62 6f 78 65 73 20 6e 65 61   small boxes nea
0400: 72 20 30 2c 30 20 2a 2f 0a 20 20 57 49 54 48 20  r 0,0 */.  WITH 
0410: 52 45 43 55 52 53 49 56 45 0a 20 20 20 20 78 28  RECURSIVE.    x(
0420: 78 29 20 41 53 20 28 56 41 4c 55 45 53 28 30 29  x) AS (VALUES(0)
0430: 20 55 4e 49 4f 4e 20 41 4c 4c 20 53 45 4c 45 43   UNION ALL SELEC
0440: 54 20 78 2b 31 20 46 52 4f 4d 20 78 20 57 48 45  T x+1 FROM x WHE
0450: 52 45 20 78 3c 34 29 2c 0a 20 20 20 20 79 28 79  RE x<4),.    y(y
0460: 29 20 41 53 20 28 56 41 4c 55 45 53 28 30 29 20  ) AS (VALUES(0) 
0470: 55 4e 49 4f 4e 20 41 4c 4c 20 53 45 4c 45 43 54  UNION ALL SELECT
0480: 20 79 2b 31 20 46 52 4f 4d 20 79 20 57 48 45 52   y+1 FROM y WHER
0490: 45 20 79 3c 34 29 0a 20 20 49 4e 53 45 52 54 20  E y<4).  INSERT 
04a0: 49 4e 54 4f 20 72 74 31 20 53 45 4c 45 43 54 20  INTO rt1 SELECT 
04b0: 78 2b 35 2a 79 2c 20 78 2c 20 78 2b 32 2c 20 79  x+5*y, x, x+2, y
04c0: 2c 20 79 2b 32 20 46 52 4f 4d 20 78 2c 20 79 3b  , y+2 FROM x, y;
04d0: 0a 0a 20 20 2f 2a 20 41 20 6c 6f 6f 73 65 72 20  ..  /* A looser 
04e0: 70 61 74 74 65 72 6e 20 6f 66 20 73 6d 61 6c 6c  pattern of small
04f0: 20 62 6f 78 65 73 20 6e 65 61 72 20 31 30 30 2c   boxes near 100,
0500: 20 30 20 2a 2f 0a 20 20 57 49 54 48 20 52 45 43   0 */.  WITH REC
0510: 55 52 53 49 56 45 0a 20 20 20 20 78 28 78 29 20  URSIVE.    x(x) 
0520: 41 53 20 28 56 41 4c 55 45 53 28 30 29 20 55 4e  AS (VALUES(0) UN
0530: 49 4f 4e 20 41 4c 4c 20 53 45 4c 45 43 54 20 78  ION ALL SELECT x
0540: 2b 31 20 46 52 4f 4d 20 78 20 57 48 45 52 45 20  +1 FROM x WHERE 
0550: 78 3c 34 29 2c 0a 20 20 20 20 79 28 79 29 20 41  x<4),.    y(y) A
0560: 53 20 28 56 41 4c 55 45 53 28 30 29 20 55 4e 49  S (VALUES(0) UNI
0570: 4f 4e 20 41 4c 4c 20 53 45 4c 45 43 54 20 79 2b  ON ALL SELECT y+
0580: 31 20 46 52 4f 4d 20 79 20 57 48 45 52 45 20 79  1 FROM y WHERE y
0590: 3c 34 29 0a 20 20 49 4e 53 45 52 54 20 49 4e 54  <4).  INSERT INT
05a0: 4f 20 72 74 31 20 53 45 4c 45 43 54 20 31 30 30  O rt1 SELECT 100
05b0: 2b 78 2b 35 2a 79 2c 20 78 2a 33 2b 31 30 30 2c  +x+5*y, x*3+100,
05c0: 20 78 2a 33 2b 31 30 32 2c 20 79 2a 33 2c 20 79   x*3+102, y*3, y
05d0: 2a 33 2b 32 20 46 52 4f 4d 20 78 2c 20 79 3b 0a  *3+2 FROM x, y;.
05e0: 0a 20 20 2f 2a 20 41 20 6c 6f 6f 73 65 72 20 70  .  /* A looser p
05f0: 61 74 74 65 72 6e 20 6f 66 20 6c 61 72 67 65 72  attern of larger
0600: 20 62 6f 78 65 73 20 6e 65 61 72 20 30 2c 20 32   boxes near 0, 2
0610: 30 30 20 2a 2f 0a 20 20 57 49 54 48 20 52 45 43  00 */.  WITH REC
0620: 55 52 53 49 56 45 0a 20 20 20 20 78 28 78 29 20  URSIVE.    x(x) 
0630: 41 53 20 28 56 41 4c 55 45 53 28 30 29 20 55 4e  AS (VALUES(0) UN
0640: 49 4f 4e 20 41 4c 4c 20 53 45 4c 45 43 54 20 78  ION ALL SELECT x
0650: 2b 31 20 46 52 4f 4d 20 78 20 57 48 45 52 45 20  +1 FROM x WHERE 
0660: 78 3c 34 29 2c 0a 20 20 20 20 79 28 79 29 20 41  x<4),.    y(y) A
0670: 53 20 28 56 41 4c 55 45 53 28 30 29 20 55 4e 49  S (VALUES(0) UNI
0680: 4f 4e 20 41 4c 4c 20 53 45 4c 45 43 54 20 79 2b  ON ALL SELECT y+
0690: 31 20 46 52 4f 4d 20 79 20 57 48 45 52 45 20 79  1 FROM y WHERE y
06a0: 3c 34 29 0a 20 20 49 4e 53 45 52 54 20 49 4e 54  <4).  INSERT INT
06b0: 4f 20 72 74 31 20 53 45 4c 45 43 54 20 32 30 30  O rt1 SELECT 200
06c0: 2b 78 2b 35 2a 79 2c 20 78 2a 37 2c 20 78 2a 37  +x+5*y, x*7, x*7
06d0: 2b 31 35 2c 20 79 2a 37 2b 32 30 30 2c 20 79 2a  +15, y*7+200, y*
06e0: 37 2b 32 31 35 20 46 52 4f 4d 20 78 2c 20 79 3b  7+215 FROM x, y;
06f0: 0a 7d 20 7b 7d 0a 0a 23 20 51 75 65 72 69 65 73  .} {}..# Queries
0700: 20 61 67 61 69 6e 73 74 20 65 61 63 68 20 6f 66   against each of
0710: 20 74 68 65 20 74 68 72 65 65 20 63 6c 75 73 74   the three clust
0720: 65 72 73 20 2a 2f 0a 64 6f 5f 65 78 65 63 73 71  ers */.do_execsq
0730: 6c 5f 74 65 73 74 20 72 74 72 65 65 45 2d 31 2e  l_test rtreeE-1.
0740: 31 20 7b 0a 20 20 53 45 4c 45 43 54 20 69 64 20  1 {.  SELECT id 
0750: 46 52 4f 4d 20 72 74 31 20 57 48 45 52 45 20 69  FROM rt1 WHERE i
0760: 64 20 4d 41 54 43 48 20 51 63 69 72 63 6c 65 28  d MATCH Qcircle(
0770: 30 2e 30 2c 20 30 2e 30 2c 20 35 30 2e 30 2c 20  0.0, 0.0, 50.0, 
0780: 33 29 20 4f 52 44 45 52 20 42 59 20 69 64 3b 0a  3) ORDER BY id;.
0790: 7d 20 7b 30 20 31 20 32 20 33 20 34 20 35 20 36  } {0 1 2 3 4 5 6
07a0: 20 37 20 38 20 39 20 31 30 20 31 31 20 31 32 20   7 8 9 10 11 12 
07b0: 31 33 20 31 34 20 31 35 20 31 36 20 31 37 20 31  13 14 15 16 17 1
07c0: 38 20 31 39 20 32 30 20 32 31 20 32 32 20 32 33  8 19 20 21 22 23
07d0: 20 32 34 7d 0a 64 6f 5f 65 78 65 63 73 71 6c 5f   24}.do_execsql_
07e0: 74 65 73 74 20 72 74 72 65 65 45 2d 31 2e 32 20  test rtreeE-1.2 
07f0: 7b 0a 20 20 53 45 4c 45 43 54 20 69 64 20 46 52  {.  SELECT id FR
0800: 4f 4d 20 72 74 31 20 57 48 45 52 45 20 69 64 20  OM rt1 WHERE id 
0810: 4d 41 54 43 48 20 51 63 69 72 63 6c 65 28 31 30  MATCH Qcircle(10
0820: 30 2e 30 2c 20 30 2e 30 2c 20 35 30 2e 30 2c 20  0.0, 0.0, 50.0, 
0830: 33 29 20 4f 52 44 45 52 20 42 59 20 69 64 3b 0a  3) ORDER BY id;.
0840: 7d 20 7b 31 30 30 20 31 30 31 20 31 30 32 20 31  } {100 101 102 1
0850: 30 33 20 31 30 34 20 31 30 35 20 31 30 36 20 31  03 104 105 106 1
0860: 30 37 20 31 30 38 20 31 30 39 20 31 31 30 20 31  07 108 109 110 1
0870: 31 31 20 31 31 32 20 31 31 33 20 31 31 34 20 31  11 112 113 114 1
0880: 31 35 20 31 31 36 20 31 31 37 20 31 31 38 20 31  15 116 117 118 1
0890: 31 39 20 31 32 30 20 31 32 31 20 31 32 32 20 31  19 120 121 122 1
08a0: 32 33 20 31 32 34 7d 0a 64 6f 5f 65 78 65 63 73  23 124}.do_execs
08b0: 71 6c 5f 74 65 73 74 20 72 74 72 65 65 45 2d 31  ql_test rtreeE-1
08c0: 2e 33 20 7b 0a 20 20 53 45 4c 45 43 54 20 69 64  .3 {.  SELECT id
08d0: 20 46 52 4f 4d 20 72 74 31 20 57 48 45 52 45 20   FROM rt1 WHERE 
08e0: 69 64 20 4d 41 54 43 48 20 51 63 69 72 63 6c 65  id MATCH Qcircle
08f0: 28 30 2e 30 2c 20 32 30 30 2e 30 2c 20 35 30 2e  (0.0, 200.0, 50.
0900: 30 2c 20 33 29 20 4f 52 44 45 52 20 42 59 20 69  0, 3) ORDER BY i
0910: 64 3b 0a 7d 20 7b 32 30 30 20 32 30 31 20 32 30  d;.} {200 201 20
0920: 32 20 32 30 33 20 32 30 34 20 32 30 35 20 32 30  2 203 204 205 20
0930: 36 20 32 30 37 20 32 30 38 20 32 30 39 20 32 31  6 207 208 209 21
0940: 30 20 32 31 31 20 32 31 32 20 32 31 33 20 32 31  0 211 212 213 21
0950: 34 20 32 31 35 20 32 31 36 20 32 31 37 20 32 31  4 215 216 217 21
0960: 38 20 32 31 39 20 32 32 30 20 32 32 31 20 32 32  8 219 220 221 22
0970: 32 20 32 32 33 20 32 32 34 7d 0a 0a 23 20 54 68  2 223 224}..# Th
0980: 65 20 51 63 69 72 63 6c 65 20 67 65 6f 6d 65 74  e Qcircle geomet
0990: 72 79 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65  ry function give
09a0: 73 20 61 20 6c 6f 77 65 72 20 73 63 6f 72 65 20  s a lower score 
09b0: 74 6f 20 6c 61 72 67 65 72 20 6c 65 61 66 2d 6e  to larger leaf-n
09c0: 6f 64 65 73 2e 0a 23 20 54 68 69 73 20 63 61 75  odes..# This cau
09d0: 73 65 73 20 74 68 65 20 32 30 30 73 20 74 6f 20  ses the 200s to 
09e0: 73 6f 72 74 20 62 65 66 6f 72 65 20 74 68 65 20  sort before the 
09f0: 31 30 30 73 20 61 6e 64 20 74 68 65 20 30 73 20  100s and the 0s 
0a00: 74 6f 20 73 6f 72 74 20 62 65 66 6f 72 65 0a 23  to sort before.#
0a10: 20 6c 61 73 74 2e 0a 23 0a 64 6f 5f 65 78 65 63   last..#.do_exec
0a20: 73 71 6c 5f 74 65 73 74 20 72 74 72 65 65 45 2d  sql_test rtreeE-
0a30: 31 2e 34 20 7b 0a 20 20 53 45 4c 45 43 54 20 69  1.4 {.  SELECT i
0a40: 64 20 46 52 4f 4d 20 72 74 31 20 57 48 45 52 45  d FROM rt1 WHERE
0a50: 20 69 64 20 4d 41 54 43 48 20 51 63 69 72 63 6c   id MATCH Qcircl
0a60: 65 28 30 2c 30 2c 31 30 30 30 2c 33 29 20 41 4e  e(0,0,1000,3) AN
0a70: 44 20 69 64 25 31 30 30 3d 3d 30 0a 7d 20 7b 32  D id%100==0.} {2
0a80: 30 30 20 31 30 30 20 30 7d 0a 0a 23 20 45 78 63  00 100 0}..# Exc
0a90: 6c 75 64 65 20 6f 64 64 20 72 6f 77 69 64 73 20  lude odd rowids 
0aa0: 6f 6e 20 61 20 64 65 70 74 68 2d 66 69 72 73 74  on a depth-first
0ab0: 20 73 65 61 72 63 68 0a 64 6f 5f 65 78 65 63 73   search.do_execs
0ac0: 71 6c 5f 74 65 73 74 20 72 74 72 65 65 45 2d 31  ql_test rtreeE-1
0ad0: 2e 35 20 7b 0a 20 20 53 45 4c 45 43 54 20 69 64  .5 {.  SELECT id
0ae0: 20 46 52 4f 4d 20 72 74 31 20 57 48 45 52 45 20   FROM rt1 WHERE 
0af0: 69 64 20 4d 41 54 43 48 20 51 63 69 72 63 6c 65  id MATCH Qcircle
0b00: 28 30 2c 30 2c 31 30 30 30 2c 34 29 20 4f 52 44  (0,0,1000,4) ORD
0b10: 45 52 20 42 59 20 2b 69 64 0a 7d 20 7b 30 20 32  ER BY +id.} {0 2
0b20: 20 34 20 36 20 38 20 31 30 20 31 32 20 31 34 20   4 6 8 10 12 14 
0b30: 31 36 20 31 38 20 32 30 20 32 32 20 32 34 20 31  16 18 20 22 24 1
0b40: 30 30 20 31 30 32 20 31 30 34 20 31 30 36 20 31  00 102 104 106 1
0b50: 30 38 20 31 31 30 20 31 31 32 20 31 31 34 20 31  08 110 112 114 1
0b60: 31 36 20 31 31 38 20 31 32 30 20 31 32 32 20 31  16 118 120 122 1
0b70: 32 34 20 32 30 30 20 32 30 32 20 32 30 34 20 32  24 200 202 204 2
0b80: 30 36 20 32 30 38 20 32 31 30 20 32 31 32 20 32  06 208 210 212 2
0b90: 31 34 20 32 31 36 20 32 31 38 20 32 32 30 20 32  14 216 218 220 2
0ba0: 32 32 20 32 32 34 7d 0a 0a 23 20 45 78 63 6c 75  22 224}..# Exclu
0bb0: 64 65 20 6f 64 64 20 72 6f 77 69 64 73 20 6f 6e  de odd rowids on
0bc0: 20 61 20 62 72 65 61 64 74 68 2d 66 69 72 73 74   a breadth-first
0bd0: 20 73 65 61 72 63 68 2e 0a 64 6f 5f 65 78 65 63   search..do_exec
0be0: 73 71 6c 5f 74 65 73 74 20 72 74 72 65 65 45 2d  sql_test rtreeE-
0bf0: 31 2e 36 20 7b 0a 20 20 53 45 4c 45 43 54 20 69  1.6 {.  SELECT i
0c00: 64 20 46 52 4f 4d 20 72 74 31 20 57 48 45 52 45  d FROM rt1 WHERE
0c10: 20 69 64 20 4d 41 54 43 48 20 51 63 69 72 63 6c   id MATCH Qcircl
0c20: 65 28 30 2c 30 2c 31 30 30 30 2c 35 29 20 4f 52  e(0,0,1000,5) OR
0c30: 44 45 52 20 42 59 20 2b 69 64 0a 7d 20 7b 30 20  DER BY +id.} {0 
0c40: 32 20 34 20 36 20 38 20 31 30 20 31 32 20 31 34  2 4 6 8 10 12 14
0c50: 20 31 36 20 31 38 20 32 30 20 32 32 20 32 34 20   16 18 20 22 24 
0c60: 31 30 30 20 31 30 32 20 31 30 34 20 31 30 36 20  100 102 104 106 
0c70: 31 30 38 20 31 31 30 20 31 31 32 20 31 31 34 20  108 110 112 114 
0c80: 31 31 36 20 31 31 38 20 31 32 30 20 31 32 32 20  116 118 120 122 
0c90: 31 32 34 20 32 30 30 20 32 30 32 20 32 30 34 20  124 200 202 204 
0ca0: 32 30 36 20 32 30 38 20 32 31 30 20 32 31 32 20  206 208 210 212 
0cb0: 32 31 34 20 32 31 36 20 32 31 38 20 32 32 30 20  214 216 218 220 
0cc0: 32 32 32 20 32 32 34 7d 0a 0a 23 20 43 6f 6e 73  222 224}..# Cons
0cd0: 74 72 75 63 74 20 61 20 6c 61 72 67 65 20 32 2d  truct a large 2-
0ce0: 44 20 52 54 72 65 65 20 77 69 74 68 20 74 68 6f  D RTree with tho
0cf0: 75 73 61 6e 64 73 20 6f 66 20 72 61 6e 64 6f 6d  usands of random
0d00: 20 65 6e 74 72 69 65 73 2e 0a 23 0a 64 6f 5f 74   entries..#.do_t
0d10: 65 73 74 20 72 74 72 65 65 45 2d 32 2e 31 20 7b  est rtreeE-2.1 {
0d20: 0a 20 20 64 62 20 65 76 61 6c 20 7b 0a 20 20 20  .  db eval {.   
0d30: 20 43 52 45 41 54 45 20 54 41 42 4c 45 20 74 32   CREATE TABLE t2
0d40: 28 69 64 2c 78 30 2c 78 31 2c 79 30 2c 79 31 29  (id,x0,x1,y0,y1)
0d50: 3b 0a 20 20 20 20 43 52 45 41 54 45 20 56 49 52  ;.    CREATE VIR
0d60: 54 55 41 4c 20 54 41 42 4c 45 20 72 74 32 20 55  TUAL TABLE rt2 U
0d70: 53 49 4e 47 20 72 74 72 65 65 28 69 64 2c 78 30  SING rtree(id,x0
0d80: 2c 78 31 2c 79 30 2c 79 31 29 3b 0a 20 20 20 20  ,x1,y0,y1);.    
0d90: 42 45 47 49 4e 3b 0a 20 20 7d 0a 20 20 65 78 70  BEGIN;.  }.  exp
0da0: 72 20 73 72 61 6e 64 28 30 29 0a 20 20 66 6f 72  r srand(0).  for
0db0: 20 7b 73 65 74 20 69 20 31 7d 20 7b 24 69 3c 3d   {set i 1} {$i<=
0dc0: 31 30 30 30 30 7d 20 7b 69 6e 63 72 20 69 7d 20  10000} {incr i} 
0dd0: 7b 0a 20 20 20 20 73 65 74 20 64 78 20 5b 65 78  {.    set dx [ex
0de0: 70 72 20 7b 69 6e 74 28 72 61 6e 64 28 29 2a 34  pr {int(rand()*4
0df0: 30 29 2b 31 7d 5d 0a 20 20 20 20 73 65 74 20 64  0)+1}].    set d
0e00: 79 20 5b 65 78 70 72 20 7b 69 6e 74 28 72 61 6e  y [expr {int(ran
0e10: 64 28 29 2a 34 30 29 2b 31 7d 5d 0a 20 20 20 20  d()*40)+1}].    
0e20: 73 65 74 20 78 30 20 5b 65 78 70 72 20 7b 69 6e  set x0 [expr {in
0e30: 74 28 72 61 6e 64 28 29 2a 28 31 30 30 30 30 20  t(rand()*(10000 
0e40: 2d 20 24 64 78 29 29 7d 5d 0a 20 20 20 20 73 65  - $dx))}].    se
0e50: 74 20 78 31 20 5b 65 78 70 72 20 7b 24 78 30 2b  t x1 [expr {$x0+
0e60: 24 64 78 7d 5d 0a 20 20 20 20 73 65 74 20 79 30  $dx}].    set y0
0e70: 20 5b 65 78 70 72 20 7b 69 6e 74 28 72 61 6e 64   [expr {int(rand
0e80: 28 29 2a 28 31 30 30 30 30 20 2d 20 24 64 79 29  ()*(10000 - $dy)
0e90: 29 7d 5d 0a 20 20 20 20 73 65 74 20 79 31 20 5b  )}].    set y1 [
0ea0: 65 78 70 72 20 7b 24 79 30 2b 24 64 79 7d 5d 0a  expr {$y0+$dy}].
0eb0: 20 20 20 20 73 65 74 20 69 64 20 5b 65 78 70 72      set id [expr
0ec0: 20 7b 24 69 2b 31 30 30 30 30 7d 5d 0a 20 20 20   {$i+10000}].   
0ed0: 20 64 62 20 65 76 61 6c 20 7b 49 4e 53 45 52 54   db eval {INSERT
0ee0: 20 49 4e 54 4f 20 74 32 20 56 41 4c 55 45 53 28   INTO t2 VALUES(
0ef0: 24 69 64 2c 24 78 30 2c 24 78 31 2c 24 79 30 2c  $id,$x0,$x1,$y0,
0f00: 24 79 31 29 7d 0a 20 20 7d 0a 20 20 64 62 20 65  $y1)}.  }.  db e
0f10: 76 61 6c 20 7b 0a 20 20 20 20 49 4e 53 45 52 54  val {.    INSERT
0f20: 20 49 4e 54 4f 20 72 74 32 20 53 45 4c 45 43 54   INTO rt2 SELECT
0f30: 20 2a 20 46 52 4f 4d 20 74 32 3b 0a 20 20 20 20   * FROM t2;.    
0f40: 43 4f 4d 4d 49 54 3b 0a 20 20 7d 0a 7d 20 7b 7d  COMMIT;.  }.} {}
0f50: 0a 0a 66 6f 72 20 7b 73 65 74 20 69 20 31 7d 20  ..for {set i 1} 
0f60: 7b 24 69 3c 3d 32 30 30 7d 20 7b 69 6e 63 72 20  {$i<=200} {incr 
0f70: 69 7d 20 7b 0a 20 20 73 65 74 20 64 78 20 5b 65  i} {.  set dx [e
0f80: 78 70 72 20 7b 69 6e 74 28 72 61 6e 64 28 29 2a  xpr {int(rand()*
0f90: 31 30 30 29 7d 5d 0a 20 20 73 65 74 20 64 79 20  100)}].  set dy 
0fa0: 5b 65 78 70 72 20 7b 69 6e 74 28 72 61 6e 64 28  [expr {int(rand(
0fb0: 29 2a 31 30 30 29 7d 5d 0a 20 20 73 65 74 20 78  )*100)}].  set x
0fc0: 30 20 5b 65 78 70 72 20 7b 69 6e 74 28 72 61 6e  0 [expr {int(ran
0fd0: 64 28 29 2a 28 31 30 30 30 30 20 2d 20 24 64 78  d()*(10000 - $dx
0fe0: 29 29 7d 5d 0a 20 20 73 65 74 20 78 31 20 5b 65  ))}].  set x1 [e
0ff0: 78 70 72 20 7b 24 78 30 2b 24 64 78 7d 5d 0a 20  xpr {$x0+$dx}]. 
1000: 20 73 65 74 20 79 30 20 5b 65 78 70 72 20 7b 69   set y0 [expr {i
1010: 6e 74 28 72 61 6e 64 28 29 2a 28 31 30 30 30 30  nt(rand()*(10000
1020: 20 2d 20 24 64 79 29 29 7d 5d 0a 20 20 73 65 74   - $dy))}].  set
1030: 20 79 31 20 5b 65 78 70 72 20 7b 24 79 30 2b 24   y1 [expr {$y0+$
1040: 64 79 7d 5d 0a 20 20 73 65 74 20 61 6e 73 20 5b  dy}].  set ans [
1050: 64 62 20 65 76 61 6c 20 7b 53 45 4c 45 43 54 20  db eval {SELECT 
1060: 69 64 20 46 52 4f 4d 20 74 32 20 57 48 45 52 45  id FROM t2 WHERE
1070: 20 78 31 3e 3d 24 78 30 20 41 4e 44 20 78 30 3c   x1>=$x0 AND x0<
1080: 3d 24 78 31 20 41 4e 44 20 79 31 3e 3d 24 79 30  =$x1 AND y1>=$y0
1090: 20 41 4e 44 20 79 30 3c 3d 24 79 31 20 4f 52 44   AND y0<=$y1 ORD
10a0: 45 52 20 42 59 20 69 64 7d 5d 0a 20 20 64 6f 5f  ER BY id}].  do_
10b0: 65 78 65 63 73 71 6c 5f 74 65 73 74 20 72 74 72  execsql_test rtr
10c0: 65 65 45 2d 32 2e 32 2e 24 69 20 7b 0a 20 20 20  eeE-2.2.$i {.   
10d0: 20 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20   SELECT id FROM 
10e0: 72 74 32 20 57 48 45 52 45 20 69 64 20 4d 41 54  rt2 WHERE id MAT
10f0: 43 48 20 62 72 65 61 64 74 68 66 69 72 73 74 73  CH breadthfirsts
1100: 65 61 72 63 68 28 24 78 30 2c 24 78 31 2c 24 79  earch($x0,$x1,$y
1110: 30 2c 24 79 31 29 20 4f 52 44 45 52 20 42 59 20  0,$y1) ORDER BY 
1120: 69 64 0a 20 20 7d 20 24 61 6e 73 0a 7d 0a 0a 23  id.  } $ans.}..#
1130: 20 52 75 6e 20 71 75 65 72 79 20 74 68 61 74 20   Run query that 
1140: 68 61 76 65 20 76 65 72 79 20 64 65 65 70 20 70  have very deep p
1150: 72 69 6f 72 69 74 79 20 71 75 65 75 65 73 0a 23  riority queues.#
1160: 0a 73 65 74 20 61 6e 73 20 5b 64 62 20 65 76 61  .set ans [db eva
1170: 6c 20 7b 53 45 4c 45 43 54 20 69 64 20 46 52 4f  l {SELECT id FRO
1180: 4d 20 74 32 20 57 48 45 52 45 20 78 31 3e 3d 30  M t2 WHERE x1>=0
1190: 20 41 4e 44 20 78 30 3c 3d 35 30 30 30 20 41 4e   AND x0<=5000 AN
11a0: 44 20 79 31 3e 3d 30 20 41 4e 44 20 79 30 3c 3d  D y1>=0 AND y0<=
11b0: 35 30 30 30 20 4f 52 44 45 52 20 42 59 20 69 64  5000 ORDER BY id
11c0: 7d 5d 0a 64 6f 5f 65 78 65 63 73 71 6c 5f 74 65  }].do_execsql_te
11d0: 73 74 20 72 74 72 65 65 45 2d 32 2e 33 20 7b 0a  st rtreeE-2.3 {.
11e0: 20 20 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d    SELECT id FROM
11f0: 20 72 74 32 20 57 48 45 52 45 20 69 64 20 4d 41   rt2 WHERE id MA
1200: 54 43 48 20 62 72 65 61 64 74 68 66 69 72 73 74  TCH breadthfirst
1210: 73 65 61 72 63 68 28 30 2c 35 30 30 30 2c 30 2c  search(0,5000,0,
1220: 35 30 30 30 29 20 4f 52 44 45 52 20 42 59 20 69  5000) ORDER BY i
1230: 64 0a 7d 20 24 61 6e 73 0a 73 65 74 20 61 6e 73  d.} $ans.set ans
1240: 20 5b 64 62 20 65 76 61 6c 20 7b 53 45 4c 45 43   [db eval {SELEC
1250: 54 20 69 64 20 46 52 4f 4d 20 74 32 20 57 48 45  T id FROM t2 WHE
1260: 52 45 20 78 31 3e 3d 30 20 41 4e 44 20 78 30 3c  RE x1>=0 AND x0<
1270: 3d 31 30 30 30 30 20 41 4e 44 20 79 31 3e 3d 30  =10000 AND y1>=0
1280: 20 41 4e 44 20 79 30 3c 3d 31 30 30 30 30 20 4f   AND y0<=10000 O
1290: 52 44 45 52 20 42 59 20 69 64 7d 5d 0a 64 6f 5f  RDER BY id}].do_
12a0: 65 78 65 63 73 71 6c 5f 74 65 73 74 20 72 74 72  execsql_test rtr
12b0: 65 65 45 2d 32 2e 34 20 7b 0a 20 20 53 45 4c 45  eeE-2.4 {.  SELE
12c0: 43 54 20 69 64 20 46 52 4f 4d 20 72 74 32 20 57  CT id FROM rt2 W
12d0: 48 45 52 45 20 69 64 20 4d 41 54 43 48 20 62 72  HERE id MATCH br
12e0: 65 61 64 74 68 66 69 72 73 74 73 65 61 72 63 68  eadthfirstsearch
12f0: 28 30 2c 31 30 30 30 30 2c 30 2c 31 30 30 30 30  (0,10000,0,10000
1300: 29 20 4f 52 44 45 52 20 42 59 20 69 64 0a 7d 20  ) ORDER BY id.} 
1310: 24 61 6e 73 0a 0a 66 69 6e 69 73 68 5f 74 65 73  $ans..finish_tes
1320: 74 0a                                            t.