/ Hex Artifact Content
Login

Artifact 304de65d484540111b896827e4261815e5dca4ce28eeecd58be648cd73452c4b:


0000: 23 20 32 30 30 38 20 4d 61 79 20 32 33 0a 23 0a  # 2008 May 23.#.
0010: 23 20 54 68 65 20 61 75 74 68 6f 72 20 64 69 73  # The author dis
0020: 63 6c 61 69 6d 73 20 63 6f 70 79 72 69 67 68 74  claims copyright
0030: 20 74 6f 20 74 68 69 73 20 73 6f 75 72 63 65 20   to this source 
0040: 63 6f 64 65 2e 20 20 49 6e 20 70 6c 61 63 65 20  code.  In place 
0050: 6f 66 0a 23 20 61 20 6c 65 67 61 6c 20 6e 6f 74  of.# a legal not
0060: 69 63 65 2c 20 68 65 72 65 20 69 73 20 61 20 62  ice, here is a b
0070: 6c 65 73 73 69 6e 67 3a 0a 23 0a 23 20 20 20 20  lessing:.#.#    
0080: 4d 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20  May you do good 
0090: 61 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 23 20  and not evil..# 
00a0: 20 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20     May you find 
00b0: 66 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20  forgiveness for 
00c0: 79 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72  yourself and for
00d0: 67 69 76 65 20 6f 74 68 65 72 73 2e 0a 23 20 20  give others..#  
00e0: 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20    May you share 
00f0: 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61  freely, never ta
0100: 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79  king more than y
0110: 6f 75 20 67 69 76 65 2e 0a 23 0a 23 2a 2a 2a 2a  ou 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 0a 23 0a 23 20 52 61 6e 64 6f 6d 69 7a  ***.#.# Randomiz
0170: 65 64 20 74 65 73 74 20 63 61 73 65 73 20 66 6f  ed test cases fo
0180: 72 20 74 68 65 20 72 74 72 65 65 20 65 78 74 65  r the rtree exte
0190: 6e 73 69 6f 6e 2e 0a 23 0a 0a 69 66 20 7b 21 5b  nsion..#..if {![
01a0: 69 6e 66 6f 20 65 78 69 73 74 73 20 74 65 73 74  info exists test
01b0: 64 69 72 5d 7d 20 7b 0a 20 20 73 65 74 20 74 65  dir]} {.  set te
01c0: 73 74 64 69 72 20 5b 66 69 6c 65 20 6a 6f 69 6e  stdir [file join
01d0: 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65 20 5b   [file dirname [
01e0: 69 6e 66 6f 20 73 63 72 69 70 74 5d 5d 20 2e 2e  info script]] ..
01f0: 20 2e 2e 20 74 65 73 74 5d 0a 7d 20 0a 73 6f 75   .. test].} .sou
0200: 72 63 65 20 5b 66 69 6c 65 20 6a 6f 69 6e 20 5b  rce [file join [
0210: 66 69 6c 65 20 64 69 72 6e 61 6d 65 20 5b 69 6e  file dirname [in
0220: 66 6f 20 73 63 72 69 70 74 5d 5d 20 72 74 72 65  fo script]] rtre
0230: 65 5f 75 74 69 6c 2e 74 63 6c 5d 0a 73 6f 75 72  e_util.tcl].sour
0240: 63 65 20 24 74 65 73 74 64 69 72 2f 74 65 73 74  ce $testdir/test
0250: 65 72 2e 74 63 6c 0a 0a 69 66 63 61 70 61 62 6c  er.tcl..ifcapabl
0260: 65 20 21 72 74 72 65 65 20 7b 0a 20 20 66 69 6e  e !rtree {.  fin
0270: 69 73 68 5f 74 65 73 74 0a 20 20 72 65 74 75 72  ish_test.  retur
0280: 6e 0a 7d 0a 0a 73 65 74 20 3a 3a 4e 52 4f 57 20  n.}..set ::NROW 
0290: 32 35 30 30 0a 69 66 20 7b 5b 69 6e 66 6f 20 65  2500.if {[info e
02a0: 78 69 73 74 73 20 47 28 69 73 71 75 69 63 6b 29  xists G(isquick)
02b0: 5d 20 26 26 20 24 47 28 69 73 71 75 69 63 6b 29  ] && $G(isquick)
02c0: 7d 20 7b 0a 20 20 73 65 74 20 3a 3a 4e 52 4f 57  } {.  set ::NROW
02d0: 20 32 35 30 0a 7d 0a 0a 69 66 63 61 70 61 62 6c   250.}..ifcapabl
02e0: 65 20 21 72 74 72 65 65 5f 69 6e 74 5f 6f 6e 6c  e !rtree_int_onl
02f0: 79 20 7b 0a 20 20 23 20 52 65 74 75 72 6e 20 61  y {.  # Return a
0300: 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69 6e 74 20   floating point 
0310: 6e 75 6d 62 65 72 20 62 65 74 77 65 65 6e 20 2d  number between -
0320: 58 20 61 6e 64 20 58 2e 0a 20 20 23 20 0a 20 20  X and X..  # .  
0330: 70 72 6f 63 20 72 61 6e 64 20 7b 58 7d 20 7b 0a  proc rand {X} {.
0340: 20 20 20 20 72 65 74 75 72 6e 20 5b 65 78 70 72      return [expr
0350: 20 7b 69 6e 74 28 28 72 61 6e 64 28 29 2d 30 2e   {int((rand()-0.
0360: 35 29 2a 31 30 32 34 2e 30 2a 24 58 29 2f 35 31  5)*1024.0*$X)/51
0370: 32 2e 30 7d 5d 0a 20 20 7d 0a 20 20 0a 20 20 23  2.0}].  }.  .  #
0380: 20 52 65 74 75 72 6e 20 61 20 70 6f 73 69 74 69   Return a positi
0390: 76 65 20 66 6c 6f 61 74 69 6e 67 20 70 6f 69 6e  ve floating poin
03a0: 74 20 6e 75 6d 62 65 72 20 6c 65 73 73 20 74 68  t number less th
03b0: 61 6e 20 6f 72 20 65 71 75 61 6c 20 74 6f 20 58  an or equal to X
03c0: 0a 20 20 23 0a 20 20 70 72 6f 63 20 72 61 6e 64  .  #.  proc rand
03d0: 69 6e 63 72 20 7b 58 7d 20 7b 0a 20 20 20 20 77  incr {X} {.    w
03e0: 68 69 6c 65 20 31 20 7b 0a 20 20 20 20 20 20 73  hile 1 {.      s
03f0: 65 74 20 72 20 5b 65 78 70 72 20 7b 69 6e 74 28  et r [expr {int(
0400: 72 61 6e 64 28 29 2a 24 58 2a 33 32 2e 30 29 2f  rand()*$X*32.0)/
0410: 33 32 2e 30 7d 5d 0a 20 20 20 20 20 20 69 66 20  32.0}].      if 
0420: 7b 24 72 3e 30 2e 30 7d 20 7b 72 65 74 75 72 6e  {$r>0.0} {return
0430: 20 24 72 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 7d   $r}.    }.  }.}
0440: 20 65 6c 73 65 20 7b 0a 20 20 23 20 46 6f 72 20   else {.  # For 
0450: 72 74 72 65 65 5f 69 6e 74 5f 6f 6e 6c 79 2c 20  rtree_int_only, 
0460: 72 65 74 75 72 6e 20 61 6e 20 6e 75 6d 62 65 72  return an number
0470: 20 62 65 74 77 65 65 6e 20 2d 58 20 61 6e 64 20   between -X and 
0480: 58 2e 0a 20 20 23 20 0a 20 20 70 72 6f 63 20 72  X..  # .  proc r
0490: 61 6e 64 20 7b 58 7d 20 7b 0a 20 20 20 20 72 65  and {X} {.    re
04a0: 74 75 72 6e 20 5b 65 78 70 72 20 7b 69 6e 74 28  turn [expr {int(
04b0: 28 72 61 6e 64 28 29 2d 30 2e 35 29 2a 32 2a 24  (rand()-0.5)*2*$
04c0: 58 29 7d 5d 0a 20 20 7d 0a 20 20 0a 20 20 23 20  X)}].  }.  .  # 
04d0: 52 65 74 75 72 6e 20 61 20 70 6f 73 69 74 69 76  Return a positiv
04e0: 65 20 69 6e 74 65 67 65 72 20 6c 65 73 73 20 74  e integer less t
04f0: 68 61 6e 20 6f 72 20 65 71 75 61 6c 20 74 6f 20  han or equal to 
0500: 58 0a 20 20 23 0a 20 20 70 72 6f 63 20 72 61 6e  X.  #.  proc ran
0510: 64 69 6e 63 72 20 7b 58 7d 20 7b 0a 20 20 20 20  dincr {X} {.    
0520: 77 68 69 6c 65 20 31 20 7b 0a 20 20 20 20 20 20  while 1 {.      
0530: 73 65 74 20 72 20 5b 65 78 70 72 20 7b 69 6e 74  set r [expr {int
0540: 28 72 61 6e 64 28 29 2a 24 58 29 2b 31 7d 5d 0a  (rand()*$X)+1}].
0550: 20 20 20 20 20 20 69 66 20 7b 24 72 3e 30 7d 20        if {$r>0} 
0560: 7b 72 65 74 75 72 6e 20 24 72 7d 0a 20 20 20 20  {return $r}.    
0570: 7d 0a 20 20 7d 0a 7d 0a 20 20 0a 23 20 53 63 72  }.  }.}.  .# Scr
0580: 61 6d 62 6c 65 20 74 68 65 20 24 69 6e 6c 69 73  amble the $inlis
0590: 74 20 69 6e 74 6f 20 61 20 72 61 6e 64 6f 6d 20  t into a random 
05a0: 6f 72 64 65 72 2e 0a 23 0a 70 72 6f 63 20 73 63  order..#.proc sc
05b0: 72 61 6d 62 6c 65 20 7b 69 6e 6c 69 73 74 7d 20  ramble {inlist} 
05c0: 7b 0a 20 20 73 65 74 20 79 20 7b 7d 0a 20 20 66  {.  set y {}.  f
05d0: 6f 72 65 61 63 68 20 78 20 24 69 6e 6c 69 73 74  oreach x $inlist
05e0: 20 7b 0a 20 20 20 20 6c 61 70 70 65 6e 64 20 79   {.    lappend y
05f0: 20 5b 6c 69 73 74 20 5b 65 78 70 72 20 7b 72 61   [list [expr {ra
0600: 6e 64 28 29 7d 5d 20 24 78 5d 0a 20 20 7d 0a 20  nd()}] $x].  }. 
0610: 20 73 65 74 20 79 20 5b 6c 73 6f 72 74 20 24 79   set y [lsort $y
0620: 5d 0a 20 20 73 65 74 20 6f 75 74 6c 69 73 74 20  ].  set outlist 
0630: 7b 7d 0a 20 20 66 6f 72 65 61 63 68 20 78 20 24  {}.  foreach x $
0640: 79 20 7b 0a 20 20 20 20 6c 61 70 70 65 6e 64 20  y {.    lappend 
0650: 6f 75 74 6c 69 73 74 20 5b 6c 69 6e 64 65 78 20  outlist [lindex 
0660: 24 78 20 31 5d 0a 20 20 7d 0a 20 20 72 65 74 75  $x 1].  }.  retu
0670: 72 6e 20 24 6f 75 74 6c 69 73 74 0a 7d 0a 0a 23  rn $outlist.}..#
0680: 20 41 6c 77 61 79 73 20 75 73 65 20 74 68 65 20   Always use the 
0690: 73 61 6d 65 20 72 61 6e 64 6f 6d 20 73 65 65 64  same random seed
06a0: 20 73 6f 20 74 68 61 74 20 74 68 65 20 73 65 71   so that the seq
06b0: 75 65 6e 63 65 20 6f 66 20 74 65 73 74 73 0a 23  uence of tests.#
06c0: 20 69 73 20 72 65 70 65 61 74 61 62 6c 65 2e 0a   is repeatable..
06d0: 23 0a 65 78 70 72 20 7b 73 72 61 6e 64 28 31 32  #.expr {srand(12
06e0: 33 34 29 7d 0a 0a 23 20 52 75 6e 20 74 68 65 73  34)}..# Run thes
06f0: 65 20 74 65 73 74 73 20 66 6f 72 20 61 6c 6c 20  e tests for all 
0700: 6e 75 6d 62 65 72 20 6f 66 20 64 69 6d 65 6e 73  number of dimens
0710: 69 6f 6e 73 20 62 65 74 77 65 65 6e 20 31 20 61  ions between 1 a
0720: 6e 64 20 35 2e 0a 23 0a 66 6f 72 20 7b 73 65 74  nd 5..#.for {set
0730: 20 6e 44 69 6d 20 31 7d 20 7b 24 6e 44 69 6d 3c   nDim 1} {$nDim<
0740: 3d 35 7d 20 7b 69 6e 63 72 20 6e 44 69 6d 7d 20  =5} {incr nDim} 
0750: 7b 0a 0a 20 20 23 20 43 6f 6e 73 74 72 75 63 74  {..  # Construct
0760: 20 61 6e 20 72 74 72 65 65 20 76 69 72 74 75 61   an rtree virtua
0770: 6c 20 74 61 62 6c 65 20 61 6e 64 20 61 6e 20 6f  l table and an o
0780: 72 64 69 6e 61 72 79 20 62 74 72 65 65 20 74 61  rdinary btree ta
0790: 62 6c 65 0a 20 20 23 20 74 6f 20 6d 69 72 72 6f  ble.  # to mirro
07a0: 72 20 69 74 2e 20 20 54 68 65 20 6f 72 64 69 6e  r it.  The ordin
07b0: 61 72 79 20 74 61 62 6c 65 20 73 68 6f 75 6c 64  ary table should
07c0: 20 62 65 20 6d 75 63 68 20 73 6c 6f 77 65 72 20   be much slower 
07d0: 28 73 69 6e 63 65 0a 20 20 23 20 69 74 20 68 61  (since.  # it ha
07e0: 73 20 74 6f 20 64 6f 20 61 20 66 75 6c 6c 20 74  s to do a full t
07f0: 61 62 6c 65 20 73 63 61 6e 29 20 62 75 74 20 73  able scan) but s
0800: 68 6f 75 6c 64 20 67 69 76 65 20 74 68 65 20 65  hould give the e
0810: 78 61 63 74 20 73 61 6d 65 0a 20 20 23 20 61 6e  xact same.  # an
0820: 73 77 65 72 73 2e 0a 20 20 23 0a 20 20 64 6f 5f  swers..  #.  do_
0830: 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44 69  test rtree4-$nDi
0840: 6d 2e 31 20 7b 0a 20 20 20 20 73 65 74 20 63 6c  m.1 {.    set cl
0850: 69 73 74 20 7b 7d 0a 20 20 20 20 73 65 74 20 63  ist {}.    set c
0860: 6b 6c 69 73 74 20 7b 7d 0a 20 20 20 20 66 6f 72  klist {}.    for
0870: 20 7b 73 65 74 20 69 20 30 7d 20 7b 24 69 3c 24   {set i 0} {$i<$
0880: 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 69 7d 20 7b  nDim} {incr i} {
0890: 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20 63  .      lappend c
08a0: 6c 69 73 74 20 6d 6e 24 69 20 6d 78 24 69 0a 20  list mn$i mx$i. 
08b0: 20 20 20 20 20 6c 61 70 70 65 6e 64 20 63 6b 6c       lappend ckl
08c0: 69 73 74 20 22 6d 6e 24 69 3c 6d 78 24 69 22 0a  ist "mn$i<mx$i".
08d0: 20 20 20 20 7d 0a 20 20 20 20 64 62 20 65 76 61      }.    db eva
08e0: 6c 20 22 44 52 4f 50 20 54 41 42 4c 45 20 49 46  l "DROP TABLE IF
08f0: 20 45 58 49 53 54 53 20 72 78 22 0a 20 20 20 20   EXISTS rx".    
0900: 64 62 20 65 76 61 6c 20 22 44 52 4f 50 20 54 41  db eval "DROP TA
0910: 42 4c 45 20 49 46 20 45 58 49 53 54 53 20 62 78  BLE IF EXISTS bx
0920: 22 0a 20 20 20 20 64 62 20 65 76 61 6c 20 22 43  ".    db eval "C
0930: 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54 41  REATE VIRTUAL TA
0940: 42 4c 45 20 72 78 20 55 53 49 4e 47 20 72 74 72  BLE rx USING rtr
0950: 65 65 28 69 64 2c 20 5b 6a 6f 69 6e 20 24 63 6c  ee(id, [join $cl
0960: 69 73 74 20 2c 5d 29 22 0a 20 20 20 20 64 62 20  ist ,])".    db 
0970: 65 76 61 6c 20 22 43 52 45 41 54 45 20 54 41 42  eval "CREATE TAB
0980: 4c 45 20 62 78 28 69 64 20 49 4e 54 45 47 45 52  LE bx(id INTEGER
0990: 20 50 52 49 4d 41 52 59 20 4b 45 59 2c 5c 0a 20   PRIMARY KEY,\. 
09a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 5b                 [
09b0: 6a 6f 69 6e 20 24 63 6c 69 73 74 20 2c 5d 2c 20  join $clist ,], 
09c0: 43 48 45 43 4b 28 20 5b 6a 6f 69 6e 20 24 63 6b  CHECK( [join $ck
09d0: 6c 69 73 74 20 7b 20 41 4e 44 20 7d 5d 20 29 29  list { AND }] ))
09e0: 22 0a 20 20 7d 20 7b 7d 0a 0a 20 20 23 20 44 6f  ".  } {}..  # Do
09f0: 20 6d 61 6e 79 20 69 6e 73 65 72 74 69 6f 6e 73   many insertions
0a00: 20 6f 66 20 73 6d 61 6c 6c 20 6f 62 6a 65 63 74   of small object
0a10: 73 2e 20 20 44 6f 20 62 6f 74 68 20 6f 76 65 72  s.  Do both over
0a20: 6c 61 70 70 69 6e 67 20 61 6e 64 0a 20 20 23 20  lapping and.  # 
0a30: 63 6f 6e 74 61 69 6e 65 64 2d 77 69 74 68 69 6e  contained-within
0a40: 20 71 75 65 72 69 65 73 20 61 66 74 65 72 20 65   queries after e
0a50: 61 63 68 20 69 6e 73 65 72 74 20 74 6f 20 76 65  ach insert to ve
0a60: 72 69 66 79 20 74 68 61 74 20 61 6c 6c 0a 20 20  rify that all.  
0a70: 23 20 69 73 20 77 65 6c 6c 2e 0a 20 20 23 0a 20  # is well..  #. 
0a80: 20 75 6e 73 65 74 20 2d 6e 6f 63 6f 6d 70 6c 61   unset -nocompla
0a90: 69 6e 20 77 68 65 72 65 0a 20 20 66 6f 72 20 7b  in where.  for {
0aa0: 73 65 74 20 69 20 31 7d 20 7b 24 69 3c 24 3a 3a  set i 1} {$i<$::
0ab0: 4e 52 4f 57 7d 20 7b 69 6e 63 72 20 69 7d 20 7b  NROW} {incr i} {
0ac0: 0a 20 20 20 20 23 20 44 6f 20 61 20 72 61 6e 64  .    # Do a rand
0ad0: 6f 6d 20 69 6e 73 65 72 74 0a 20 20 20 20 23 0a  om insert.    #.
0ae0: 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65      do_test rtre
0af0: 65 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 31 20  e4-$nDim.2.$i.1 
0b00: 7b 0a 20 20 20 20 20 20 73 65 74 20 76 6c 69 73  {.      set vlis
0b10: 74 20 7b 7d 0a 20 20 20 20 20 20 66 6f 72 20 7b  t {}.      for {
0b20: 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44  set j 0} {$j<$nD
0b30: 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20  im} {incr j} {. 
0b40: 20 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72         set mn [r
0b50: 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20  and 10000].     
0b60: 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20     set mx [expr 
0b70: 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35  {$mn+[randincr 5
0b80: 30 5d 7d 5d 0a 20 20 20 20 20 20 20 20 6c 61 70  0]}].        lap
0b90: 70 65 6e 64 20 76 6c 69 73 74 20 24 6d 6e 20 24  pend vlist $mn $
0ba0: 6d 78 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20  mx.      }.     
0bb0: 20 64 62 20 65 76 61 6c 20 22 49 4e 53 45 52 54   db eval "INSERT
0bc0: 20 49 4e 54 4f 20 72 78 20 56 41 4c 55 45 53 28   INTO rx VALUES(
0bd0: 4e 55 4c 4c 2c 20 5b 6a 6f 69 6e 20 24 76 6c 69  NULL, [join $vli
0be0: 73 74 20 2c 5d 29 22 0a 20 20 20 20 20 20 64 62  st ,])".      db
0bf0: 20 65 76 61 6c 20 22 49 4e 53 45 52 54 20 49 4e   eval "INSERT IN
0c00: 54 4f 20 62 78 20 56 41 4c 55 45 53 28 4e 55 4c  TO bx VALUES(NUL
0c10: 4c 2c 20 5b 6a 6f 69 6e 20 24 76 6c 69 73 74 20  L, [join $vlist 
0c20: 2c 5d 29 22 0a 20 20 20 20 7d 20 7b 7d 0a 0a 20  ,])".    } {}.. 
0c30: 20 20 20 23 20 44 6f 20 61 20 63 6f 6e 74 61 69     # Do a contai
0c40: 6e 65 64 2d 69 6e 20 71 75 65 72 79 20 6f 6e 20  ned-in query on 
0c50: 61 6c 6c 20 64 69 6d 65 6e 73 69 6f 6e 73 0a 20  all dimensions. 
0c60: 20 20 20 23 0a 20 20 20 20 73 65 74 20 77 68 65     #.    set whe
0c70: 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72 20 7b 73  re {}.    for {s
0c80: 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69  et j 0} {$j<$nDi
0c90: 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20  m} {incr j} {.  
0ca0: 20 20 20 20 73 65 74 20 6d 6e 20 5b 72 61 6e 64      set mn [rand
0cb0: 20 31 30 30 30 30 5d 0a 20 20 20 20 20 20 73 65   10000].      se
0cc0: 74 20 6d 78 20 5b 65 78 70 72 20 7b 24 6d 6e 2b  t mx [expr {$mn+
0cd0: 5b 72 61 6e 64 69 6e 63 72 20 35 30 30 5d 7d 5d  [randincr 500]}]
0ce0: 0a 20 20 20 20 20 20 6c 61 70 70 65 6e 64 20 77  .      lappend w
0cf0: 68 65 72 65 20 6d 6e 24 6a 3e 3d 24 6d 6e 20 6d  here mn$j>=$mn m
0d00: 78 24 6a 3c 3d 24 6d 78 0a 20 20 20 20 7d 0a 20  x$j<=$mx.    }. 
0d10: 20 20 20 73 65 74 20 77 68 65 72 65 20 22 57 48     set where "WH
0d20: 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65  ERE [join $where
0d30: 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64   { AND }]".    d
0d40: 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e  o_test rtree4-$n
0d50: 44 69 6d 2e 32 2e 24 69 2e 32 20 7b 0a 20 20 20  Dim.2.$i.2 {.   
0d60: 20 20 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b     list $where [
0d70: 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20  db eval "SELECT 
0d80: 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72  id FROM rx $wher
0d90: 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a  e ORDER BY id"].
0da0: 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65      } [list $whe
0db0: 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c  re [db eval "SEL
0dc0: 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24  ECT id FROM bx $
0dd0: 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69  where ORDER BY i
0de0: 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61  d"]]..    # Do a
0df0: 6e 20 6f 76 65 72 6c 61 70 73 20 71 75 65 72 79  n overlaps query
0e00: 20 6f 6e 20 61 6c 6c 20 64 69 6d 65 6e 73 69 6f   on all dimensio
0e10: 6e 73 0a 20 20 20 20 23 0a 20 20 20 20 73 65 74  ns.    #.    set
0e20: 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f   where {}.    fo
0e30: 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c  r {set j 0} {$j<
0e40: 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20  $nDim} {incr j} 
0e50: 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b  {.      set mn [
0e60: 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20  rand 10000].    
0e70: 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b    set mx [expr {
0e80: 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30  $mn+[randincr 50
0e90: 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65  0]}].      lappe
0ea0: 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 3d 24  nd where mx$j>=$
0eb0: 6d 6e 20 6d 6e 24 6a 3c 3d 24 6d 78 0a 20 20 20  mn mn$j<=$mx.   
0ec0: 20 7d 0a 20 20 20 20 73 65 74 20 77 68 65 72 65   }.    set where
0ed0: 20 22 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77   "WHERE [join $w
0ee0: 68 65 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20  here { AND }]". 
0ef0: 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65     do_test rtree
0f00: 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20 7b  4-$nDim.2.$i.3 {
0f10: 0a 20 20 20 20 20 20 6c 69 73 74 20 24 77 68 65  .      list $whe
0f20: 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c  re [db eval "SEL
0f30: 45 43 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24  ECT id FROM rx $
0f40: 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69  where ORDER BY i
0f50: 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20  d"].    } [list 
0f60: 24 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20  $where [db eval 
0f70: 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20  "SELECT id FROM 
0f80: 62 78 20 24 77 68 65 72 65 20 4f 52 44 45 52 20  bx $where ORDER 
0f90: 42 59 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20  BY id"]]..    # 
0fa0: 44 6f 20 61 20 63 6f 6e 74 61 69 6e 65 64 2d 69  Do a contained-i
0fb0: 6e 20 71 75 65 72 79 20 77 69 74 68 20 73 75 72  n query with sur
0fc0: 70 6c 75 73 20 63 6f 6e 74 72 61 69 6e 74 73 20  plus contraints 
0fd0: 61 74 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67  at the beginning
0fe0: 2e 0a 20 20 20 20 23 20 54 68 69 73 20 73 68 6f  ..    # This sho
0ff0: 75 6c 64 20 66 6f 72 63 65 20 61 20 66 75 6c 6c  uld force a full
1000: 2d 74 61 62 6c 65 20 73 63 61 6e 20 6f 6e 20 74  -table scan on t
1010: 68 65 20 72 74 72 65 65 2e 0a 20 20 20 20 23 0a  he rtree..    #.
1020: 20 20 20 20 73 65 74 20 77 68 65 72 65 20 7b 7d      set where {}
1030: 0a 20 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20  .    for {set j 
1040: 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69  0} {$j<$nDim} {i
1050: 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 6c  ncr j} {.      l
1060: 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d 6e 24  append where mn$
1070: 6a 3e 2d 31 30 30 30 30 20 6d 78 24 6a 3c 31 30  j>-10000 mx$j<10
1080: 30 30 30 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f  000.    }.    fo
1090: 72 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c  r {set j 0} {$j<
10a0: 24 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20  $nDim} {incr j} 
10b0: 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b  {.      set mn [
10c0: 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20  rand 10000].    
10d0: 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b    set mx [expr {
10e0: 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30  $mn+[randincr 50
10f0: 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65  0]}].      lappe
1100: 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e 3d 24  nd where mn$j>=$
1110: 6d 6e 20 6d 78 24 6a 3c 3d 24 6d 78 0a 20 20 20  mn mx$j<=$mx.   
1120: 20 7d 0a 20 20 20 20 73 65 74 20 77 68 65 72 65   }.    set where
1130: 20 22 57 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77   "WHERE [join $w
1140: 68 65 72 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20  here { AND }]". 
1150: 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72 65 65     do_test rtree
1160: 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 33 20 7b  4-$nDim.2.$i.3 {
1170: 0a 20 20 20 20 20 20 6c 69 73 74 20 24 77 68 65  .      list $whe
1180: 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c  re [db eval "SEL
1190: 45 43 54 20 69 64 20 46 52 4f 4d 20 72 78 20 24  ECT id FROM rx $
11a0: 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20 69  where ORDER BY i
11b0: 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20  d"].    } [list 
11c0: 24 77 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20  $where [db eval 
11d0: 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20  "SELECT id FROM 
11e0: 62 78 20 24 77 68 65 72 65 20 4f 52 44 45 52 20  bx $where ORDER 
11f0: 42 59 20 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20  BY id"]]..    # 
1200: 44 6f 20 61 6e 20 6f 76 65 72 6c 61 70 73 20 71  Do an overlaps q
1210: 75 65 72 79 20 77 69 74 68 20 73 75 72 70 6c 75  uery with surplu
1220: 73 20 63 6f 6e 74 72 61 69 6e 74 73 20 61 74 20  s contraints at 
1230: 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 2e 0a 20  the beginning.. 
1240: 20 20 20 23 20 54 68 69 73 20 73 68 6f 75 6c 64     # This should
1250: 20 66 6f 72 63 65 20 61 20 66 75 6c 6c 2d 74 61   force a full-ta
1260: 62 6c 65 20 73 63 61 6e 20 6f 6e 20 74 68 65 20  ble scan on the 
1270: 72 74 72 65 65 2e 0a 20 20 20 20 23 0a 20 20 20  rtree..    #.   
1280: 20 73 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20   set where {}.  
1290: 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d 20    for {set j 0} 
12a0: 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63 72  {$j<$nDim} {incr
12b0: 20 6a 7d 20 7b 0a 20 20 20 20 20 20 6c 61 70 70   j} {.      lapp
12c0: 65 6e 64 20 77 68 65 72 65 20 6d 6e 24 6a 3e 3d  end where mn$j>=
12d0: 2d 31 30 30 30 30 20 6d 78 24 6a 3c 3d 31 30 30  -10000 mx$j<=100
12e0: 30 30 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f 72  00.    }.    for
12f0: 20 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24   {set j 0} {$j<$
1300: 6e 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b  nDim} {incr j} {
1310: 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20 5b 72  .      set mn [r
1320: 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20  and 10000].     
1330: 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20 7b 24   set mx [expr {$
1340: 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35 30 30  mn+[randincr 500
1350: 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70 65 6e  ]}].      lappen
1360: 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 24 6d 6e  d where mx$j>$mn
1370: 20 6d 6e 24 6a 3c 24 6d 78 0a 20 20 20 20 7d 0a   mn$j<$mx.    }.
1380: 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22 57      set where "W
1390: 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72  HERE [join $wher
13a0: 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20  e { AND }]".    
13b0: 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24  do_test rtree4-$
13c0: 6e 44 69 6d 2e 32 2e 24 69 2e 34 20 7b 0a 20 20  nDim.2.$i.4 {.  
13d0: 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65 20      list $where 
13e0: 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54  [db eval "SELECT
13f0: 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65   id FROM rx $whe
1400: 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d  re ORDER BY id"]
1410: 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68  .    } [list $wh
1420: 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45  ere [db eval "SE
1430: 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20  LECT id FROM bx 
1440: 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20  $where ORDER BY 
1450: 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20  id"]]..    # Do 
1460: 61 20 63 6f 6e 74 61 69 6e 65 64 2d 69 6e 20 71  a contained-in q
1470: 75 65 72 79 20 77 69 74 68 20 73 75 72 70 6c 75  uery with surplu
1480: 73 20 63 6f 6e 74 72 61 69 6e 74 73 20 61 74 20  s contraints at 
1490: 74 68 65 20 65 6e 64 0a 20 20 20 20 23 0a 20 20  the end.    #.  
14a0: 20 20 73 65 74 20 77 68 65 72 65 20 7b 7d 0a 20    set where {}. 
14b0: 20 20 20 66 6f 72 20 7b 73 65 74 20 6a 20 30 7d     for {set j 0}
14c0: 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b 69 6e 63   {$j<$nDim} {inc
14d0: 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20 73 65 74  r j} {.      set
14e0: 20 6d 6e 20 5b 72 61 6e 64 20 31 30 30 30 30 5d   mn [rand 10000]
14f0: 0a 20 20 20 20 20 20 73 65 74 20 6d 78 20 5b 65  .      set mx [e
1500: 78 70 72 20 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e  xpr {$mn+[randin
1510: 63 72 20 35 30 30 5d 7d 5d 0a 20 20 20 20 20 20  cr 500]}].      
1520: 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d 6e  lappend where mn
1530: 24 6a 3e 3d 24 6d 6e 20 6d 78 24 6a 3c 24 6d 78  $j>=$mn mx$j<$mx
1540: 0a 20 20 20 20 7d 0a 20 20 20 20 66 6f 72 20 7b  .    }.    for {
1550: 73 65 74 20 6a 20 5b 65 78 70 72 20 7b 24 6e 44  set j [expr {$nD
1560: 69 6d 2d 31 7d 5d 7d 20 7b 24 6a 3e 3d 30 7d 20  im-1}]} {$j>=0} 
1570: 7b 69 6e 63 72 20 6a 20 2d 31 7d 20 7b 0a 20 20  {incr j -1} {.  
1580: 20 20 20 20 6c 61 70 70 65 6e 64 20 77 68 65 72      lappend wher
1590: 65 20 6d 6e 24 6a 3e 3d 2d 31 30 30 30 30 20 6d  e mn$j>=-10000 m
15a0: 78 24 6a 3c 31 30 30 30 30 0a 20 20 20 20 7d 0a  x$j<10000.    }.
15b0: 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22 57      set where "W
15c0: 48 45 52 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72  HERE [join $wher
15d0: 65 20 7b 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20  e { AND }]".    
15e0: 64 6f 5f 74 65 73 74 20 72 74 72 65 65 34 2d 24  do_test rtree4-$
15f0: 6e 44 69 6d 2e 32 2e 24 69 2e 35 20 7b 0a 20 20  nDim.2.$i.5 {.  
1600: 20 20 20 20 6c 69 73 74 20 24 77 68 65 72 65 20      list $where 
1610: 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54  [db eval "SELECT
1620: 20 69 64 20 46 52 4f 4d 20 72 78 20 24 77 68 65   id FROM rx $whe
1630: 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d  re ORDER BY id"]
1640: 0a 20 20 20 20 7d 20 5b 6c 69 73 74 20 24 77 68  .    } [list $wh
1650: 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53 45  ere [db eval "SE
1660: 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 62 78 20  LECT id FROM bx 
1670: 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59 20  $where ORDER BY 
1680: 69 64 22 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20  id"]]..    # Do 
1690: 61 6e 20 6f 76 65 72 6c 61 70 73 20 71 75 65 72  an overlaps quer
16a0: 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20 63  y with surplus c
16b0: 6f 6e 74 72 61 69 6e 74 73 20 61 74 20 74 68 65  ontraints at the
16c0: 20 65 6e 64 0a 20 20 20 20 23 0a 20 20 20 20 73   end.    #.    s
16d0: 65 74 20 77 68 65 72 65 20 7b 7d 0a 20 20 20 20  et where {}.    
16e0: 66 6f 72 20 7b 73 65 74 20 6a 20 5b 65 78 70 72  for {set j [expr
16f0: 20 7b 24 6e 44 69 6d 2d 31 7d 5d 7d 20 7b 24 6a   {$nDim-1}]} {$j
1700: 3e 3d 30 7d 20 7b 69 6e 63 72 20 6a 20 2d 31 7d  >=0} {incr j -1}
1710: 20 7b 0a 20 20 20 20 20 20 73 65 74 20 6d 6e 20   {.      set mn 
1720: 5b 72 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20  [rand 10000].   
1730: 20 20 20 73 65 74 20 6d 78 20 5b 65 78 70 72 20     set mx [expr 
1740: 7b 24 6d 6e 2b 5b 72 61 6e 64 69 6e 63 72 20 35  {$mn+[randincr 5
1750: 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70  00]}].      lapp
1760: 65 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 24  end where mx$j>$
1770: 6d 6e 20 6d 6e 24 6a 3c 3d 24 6d 78 0a 20 20 20  mn mn$j<=$mx.   
1780: 20 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74 20   }.    for {set 
1790: 6a 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20  j 0} {$j<$nDim} 
17a0: 7b 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20  {incr j} {.     
17b0: 20 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20 6d   lappend where m
17c0: 78 24 6a 3e 2d 31 30 30 30 30 20 6d 6e 24 6a 3c  x$j>-10000 mn$j<
17d0: 3d 31 30 30 30 30 0a 20 20 20 20 7d 0a 20 20 20  =10000.    }.   
17e0: 20 73 65 74 20 77 68 65 72 65 20 22 57 48 45 52   set where "WHER
17f0: 45 20 5b 6a 6f 69 6e 20 24 77 68 65 72 65 20 7b  E [join $where {
1800: 20 41 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f 5f   AND }]".    do_
1810: 74 65 73 74 20 72 74 72 65 65 34 2d 24 6e 44 69  test rtree4-$nDi
1820: 6d 2e 32 2e 24 69 2e 36 20 7b 0a 20 20 20 20 20  m.2.$i.6 {.     
1830: 20 6c 69 73 74 20 24 77 68 65 72 65 20 5b 64 62   list $where [db
1840: 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64   eval "SELECT id
1850: 20 46 52 4f 4d 20 72 78 20 24 77 68 65 72 65 20   FROM rx $where 
1860: 4f 52 44 45 52 20 42 59 20 69 64 22 5d 0a 20 20  ORDER BY id"].  
1870: 20 20 7d 20 5b 6c 69 73 74 20 24 77 68 65 72 65    } [list $where
1880: 20 5b 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43   [db eval "SELEC
1890: 54 20 69 64 20 46 52 4f 4d 20 62 78 20 24 77 68  T id FROM bx $wh
18a0: 65 72 65 20 4f 52 44 45 52 20 42 59 20 69 64 22  ere ORDER BY id"
18b0: 5d 5d 0a 0a 20 20 20 20 23 20 44 6f 20 61 20 63  ]]..    # Do a c
18c0: 6f 6e 74 61 69 6e 65 64 2d 69 6e 20 71 75 65 72  ontained-in quer
18d0: 79 20 77 69 74 68 20 73 75 72 70 6c 75 73 20 63  y with surplus c
18e0: 6f 6e 74 72 61 69 6e 74 73 20 77 68 65 72 65 20  ontraints where 
18f0: 74 68 65 20 0a 20 20 20 20 23 20 63 6f 6e 73 74  the .    # const
1900: 72 61 69 6e 74 73 20 61 70 70 65 61 72 20 69 6e  raints appear in
1910: 20 61 20 72 61 6e 64 6f 6d 20 6f 72 64 65 72 2e   a random order.
1920: 0a 20 20 20 20 23 0a 20 20 20 20 73 65 74 20 77  .    #.    set w
1930: 68 65 72 65 20 7b 7d 0a 20 20 20 20 66 6f 72 20  here {}.    for 
1940: 7b 73 65 74 20 6a 20 30 7d 20 7b 24 6a 3c 24 6e  {set j 0} {$j<$n
1950: 44 69 6d 7d 20 7b 69 6e 63 72 20 6a 7d 20 7b 0a  Dim} {incr j} {.
1960: 20 20 20 20 20 20 73 65 74 20 6d 6e 31 20 5b 72        set mn1 [r
1970: 61 6e 64 20 31 30 30 30 30 5d 0a 20 20 20 20 20  and 10000].     
1980: 20 73 65 74 20 6d 6e 32 20 5b 65 78 70 72 20 7b   set mn2 [expr {
1990: 24 6d 6e 31 2b 5b 72 61 6e 64 69 6e 63 72 20 31  $mn1+[randincr 1
19a0: 30 30 5d 7d 5d 0a 20 20 20 20 20 20 73 65 74 20  00]}].      set 
19b0: 6d 78 31 20 5b 65 78 70 72 20 7b 24 6d 6e 32 2b  mx1 [expr {$mn2+
19c0: 5b 72 61 6e 64 69 6e 63 72 20 34 30 30 5d 7d 5d  [randincr 400]}]
19d0: 0a 20 20 20 20 20 20 73 65 74 20 6d 78 32 20 5b  .      set mx2 [
19e0: 65 78 70 72 20 7b 24 6d 78 31 2b 5b 72 61 6e 64  expr {$mx1+[rand
19f0: 69 6e 63 72 20 31 30 30 5d 7d 5d 0a 20 20 20 20  incr 100]}].    
1a00: 20 20 6c 61 70 70 65 6e 64 20 77 68 65 72 65 20    lappend where 
1a10: 6d 6e 24 6a 3e 3d 24 6d 6e 31 20 6d 6e 24 6a 3e  mn$j>=$mn1 mn$j>
1a20: 24 6d 6e 32 20 6d 78 24 6a 3c 24 6d 78 31 20 6d  $mn2 mx$j<$mx1 m
1a30: 78 24 6a 3c 3d 24 6d 78 32 0a 20 20 20 20 7d 0a  x$j<=$mx2.    }.
1a40: 20 20 20 20 73 65 74 20 77 68 65 72 65 20 22 57      set where "W
1a50: 48 45 52 45 20 5b 6a 6f 69 6e 20 5b 73 63 72 61  HERE [join [scra
1a60: 6d 62 6c 65 20 24 77 68 65 72 65 5d 20 7b 20 41  mble $where] { A
1a70: 4e 44 20 7d 5d 22 0a 20 20 20 20 64 6f 5f 74 65  ND }]".    do_te
1a80: 73 74 20 72 74 72 65 65 34 2d 24 6e 44 69 6d 2e  st rtree4-$nDim.
1a90: 32 2e 24 69 2e 37 20 7b 0a 20 20 20 20 20 20 6c  2.$i.7 {.      l
1aa0: 69 73 74 20 24 77 68 65 72 65 20 5b 64 62 20 65  ist $where [db e
1ab0: 76 61 6c 20 22 53 45 4c 45 43 54 20 69 64 20 46  val "SELECT id F
1ac0: 52 4f 4d 20 72 78 20 24 77 68 65 72 65 20 4f 52  ROM rx $where OR
1ad0: 44 45 52 20 42 59 20 69 64 22 5d 0a 20 20 20 20  DER BY id"].    
1ae0: 7d 20 5b 6c 69 73 74 20 24 77 68 65 72 65 20 5b  } [list $where [
1af0: 64 62 20 65 76 61 6c 20 22 53 45 4c 45 43 54 20  db eval "SELECT 
1b00: 69 64 20 46 52 4f 4d 20 62 78 20 24 77 68 65 72  id FROM bx $wher
1b10: 65 20 4f 52 44 45 52 20 42 59 20 69 64 22 5d 5d  e ORDER BY id"]]
1b20: 0a 0a 20 20 20 20 23 20 44 6f 20 61 6e 20 6f 76  ..    # Do an ov
1b30: 65 72 6c 61 70 73 20 71 75 65 72 79 20 77 69 74  erlaps query wit
1b40: 68 20 73 75 72 70 6c 75 73 20 63 6f 6e 74 72 61  h surplus contra
1b50: 69 6e 74 73 20 77 68 65 72 65 20 74 68 65 0a 20  ints where the. 
1b60: 20 20 20 23 20 63 6f 6e 73 74 72 61 69 6e 74 73     # constraints
1b70: 20 61 70 70 65 61 72 20 69 6e 20 61 20 72 61 6e   appear in a ran
1b80: 64 6f 6d 20 6f 72 64 65 72 2e 0a 20 20 20 20 23  dom order..    #
1b90: 0a 20 20 20 20 73 65 74 20 77 68 65 72 65 20 7b  .    set where {
1ba0: 7d 0a 20 20 20 20 66 6f 72 20 7b 73 65 74 20 6a  }.    for {set j
1bb0: 20 30 7d 20 7b 24 6a 3c 24 6e 44 69 6d 7d 20 7b   0} {$j<$nDim} {
1bc0: 69 6e 63 72 20 6a 7d 20 7b 0a 20 20 20 20 20 20  incr j} {.      
1bd0: 73 65 74 20 6d 6e 31 20 5b 72 61 6e 64 20 31 30  set mn1 [rand 10
1be0: 30 30 30 5d 0a 20 20 20 20 20 20 73 65 74 20 6d  000].      set m
1bf0: 6e 32 20 5b 65 78 70 72 20 7b 24 6d 6e 31 2b 5b  n2 [expr {$mn1+[
1c00: 72 61 6e 64 69 6e 63 72 20 31 30 30 5d 7d 5d 0a  randincr 100]}].
1c10: 20 20 20 20 20 20 73 65 74 20 6d 78 31 20 5b 65        set mx1 [e
1c20: 78 70 72 20 7b 24 6d 6e 32 2b 5b 72 61 6e 64 69  xpr {$mn2+[randi
1c30: 6e 63 72 20 34 30 30 5d 7d 5d 0a 20 20 20 20 20  ncr 400]}].     
1c40: 20 73 65 74 20 6d 78 32 20 5b 65 78 70 72 20 7b   set mx2 [expr {
1c50: 24 6d 78 31 2b 5b 72 61 6e 64 69 6e 63 72 20 31  $mx1+[randincr 1
1c60: 30 30 5d 7d 5d 0a 20 20 20 20 20 20 6c 61 70 70  00]}].      lapp
1c70: 65 6e 64 20 77 68 65 72 65 20 6d 78 24 6a 3e 3d  end where mx$j>=
1c80: 24 6d 6e 31 20 6d 78 24 6a 3e 24 6d 6e 32 20 6d  $mn1 mx$j>$mn2 m
1c90: 6e 24 6a 3c 24 6d 78 31 20 6d 6e 24 6a 3c 3d 24  n$j<$mx1 mn$j<=$
1ca0: 6d 78 32 0a 20 20 20 20 7d 0a 20 20 20 20 73 65  mx2.    }.    se
1cb0: 74 20 77 68 65 72 65 20 22 57 48 45 52 45 20 5b  t where "WHERE [
1cc0: 6a 6f 69 6e 20 5b 73 63 72 61 6d 62 6c 65 20 24  join [scramble $
1cd0: 77 68 65 72 65 5d 20 7b 20 41 4e 44 20 7d 5d 22  where] { AND }]"
1ce0: 0a 20 20 20 20 64 6f 5f 74 65 73 74 20 72 74 72  .    do_test rtr
1cf0: 65 65 34 2d 24 6e 44 69 6d 2e 32 2e 24 69 2e 38  ee4-$nDim.2.$i.8
1d00: 20 7b 0a 20 20 20 20 20 20 6c 69 73 74 20 24 77   {.      list $w
1d10: 68 65 72 65 20 5b 64 62 20 65 76 61 6c 20 22 53  here [db eval "S
1d20: 45 4c 45 43 54 20 69 64 20 46 52 4f 4d 20 72 78  ELECT id FROM rx
1d30: 20 24 77 68 65 72 65 20 4f 52 44 45 52 20 42 59   $where ORDER BY
1d40: 20 69 64 22 5d 0a 20 20 20 20 7d 20 5b 6c 69 73   id"].    } [lis
1d50: 74 20 24 77 68 65 72 65 20 5b 64 62 20 65 76 61  t $where [db eva
1d60: 6c 20 22 53 45 4c 45 43 54 20 69 64 20 46 52 4f  l "SELECT id FRO
1d70: 4d 20 62 78 20 24 77 68 65 72 65 20 4f 52 44 45  M bx $where ORDE
1d80: 52 20 42 59 20 69 64 22 5d 5d 0a 20 20 7d 0a 0a  R BY id"]].  }..
1d90: 20 20 64 6f 5f 72 74 72 65 65 5f 69 6e 74 65 67    do_rtree_integ
1da0: 72 69 74 79 5f 74 65 73 74 20 72 74 72 65 65 34  rity_test rtree4
1db0: 2d 24 6e 44 69 6d 2e 33 20 72 78 0a 7d 0a 0a 65  -$nDim.3 rx.}..e
1dc0: 78 70 61 6e 64 5f 61 6c 6c 5f 73 71 6c 20 64 62  xpand_all_sql db
1dd0: 0a 66 69 6e 69 73 68 5f 74 65 73 74 0a           .finish_test.