/ Hex Artifact Content
Login

Artifact db734b4c5e75fed6acc56d9701f2235345acfdec750b5fc7b587936f5f6bceed:


0000: 23 20 32 30 30 38 20 46 65 62 20 31 39 0a 23 0a  # 2008 Feb 19.#.
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 54 68 69 73 20 66 69 6c  ***.#.# This fil
0170: 65 20 63 6f 6e 74 61 69 6e 73 20 54 63 6c 20 63  e contains Tcl c
0180: 6f 64 65 20 74 68 61 74 20 6d 61 79 20 62 65 20  ode that may be 
0190: 75 73 65 66 75 6c 20 66 6f 72 20 74 65 73 74 69  useful for testi
01a0: 6e 67 20 6f 72 0a 23 20 61 6e 61 6c 79 7a 69 6e  ng or.# analyzin
01b0: 67 20 72 2d 74 72 65 65 20 73 74 72 75 63 74 75  g r-tree structu
01c0: 72 65 73 20 63 72 65 61 74 65 64 20 77 69 74 68  res created with
01d0: 20 74 68 69 73 20 6d 6f 64 75 6c 65 2e 20 49 74   this module. It
01e0: 20 69 73 0a 23 20 75 73 65 64 20 62 79 20 62 6f   is.# used by bo
01f0: 74 68 20 74 65 73 74 20 70 72 6f 63 65 64 75 72  th test procedur
0200: 65 73 20 61 6e 64 20 74 68 65 20 72 2d 74 72 65  es and the r-tre
0210: 65 20 76 69 65 77 65 72 20 61 70 70 6c 69 63 61  e viewer applica
0220: 74 69 6f 6e 2e 0a 23 0a 0a 0a 23 2d 2d 2d 2d 2d  tion..#...#-----
0230: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0240: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0250: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0260: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0270: 2d 2d 2d 2d 2d 0a 23 20 50 55 42 4c 49 43 20 41  -----.# PUBLIC A
0280: 50 49 3a 0a 23 0a 23 20 20 20 72 74 72 65 65 5f  PI:.#.#   rtree_
0290: 64 65 70 74 68 0a 23 20 20 20 72 74 72 65 65 5f  depth.#   rtree_
02a0: 6e 64 69 6d 0a 23 20 20 20 72 74 72 65 65 5f 6e  ndim.#   rtree_n
02b0: 6f 64 65 0a 23 20 20 20 72 74 72 65 65 5f 6d 69  ode.#   rtree_mi
02c0: 6e 63 65 6c 6c 73 0a 23 20 20 20 72 74 72 65 65  ncells.#   rtree
02d0: 5f 63 68 65 63 6b 0a 23 20 20 20 72 74 72 65 65  _check.#   rtree
02e0: 5f 64 75 6d 70 0a 23 20 20 20 72 74 72 65 65 5f  _dump.#   rtree_
02f0: 74 72 65 65 64 75 6d 70 0a 23 0a 0a 70 72 6f 63  treedump.#..proc
0300: 20 72 74 72 65 65 5f 64 65 70 74 68 20 7b 64 62   rtree_depth {db
0310: 20 7a 54 61 62 7d 20 7b 0a 20 20 24 64 62 20 6f   zTab} {.  $db o
0320: 6e 65 20 22 53 45 4c 45 43 54 20 72 74 72 65 65  ne "SELECT rtree
0330: 64 65 70 74 68 28 64 61 74 61 29 20 46 52 4f 4d  depth(data) FROM
0340: 20 24 7b 7a 54 61 62 7d 5f 6e 6f 64 65 20 57 48   ${zTab}_node WH
0350: 45 52 45 20 6e 6f 64 65 6e 6f 3d 31 22 0a 7d 0a  ERE nodeno=1".}.
0360: 0a 70 72 6f 63 20 72 74 72 65 65 5f 6e 6f 64 65  .proc rtree_node
0370: 64 65 70 74 68 20 7b 64 62 20 7a 54 61 62 20 69  depth {db zTab i
0380: 4e 6f 64 65 7d 20 7b 0a 20 20 73 65 74 20 69 44  Node} {.  set iD
0390: 65 70 74 68 20 5b 72 74 72 65 65 5f 64 65 70 74  epth [rtree_dept
03a0: 68 20 24 64 62 20 24 7a 54 61 62 5d 0a 20 20 0a  h $db $zTab].  .
03b0: 20 20 73 65 74 20 69 69 20 24 69 4e 6f 64 65 0a    set ii $iNode.
03c0: 20 20 77 68 69 6c 65 20 7b 24 69 69 20 21 3d 20    while {$ii != 
03d0: 31 7d 20 7b 0a 20 20 20 20 73 65 74 20 73 71 6c  1} {.    set sql
03e0: 20 22 53 45 4c 45 43 54 20 70 61 72 65 6e 74 6e   "SELECT parentn
03f0: 6f 64 65 20 46 52 4f 4d 20 24 7b 7a 54 61 62 7d  ode FROM ${zTab}
0400: 5f 70 61 72 65 6e 74 20 57 48 45 52 45 20 6e 6f  _parent WHERE no
0410: 64 65 6e 6f 20 3d 20 24 69 69 22 0a 20 20 20 20  deno = $ii".    
0420: 73 65 74 20 69 69 20 5b 64 62 20 6f 6e 65 20 24  set ii [db one $
0430: 73 71 6c 5d 0a 20 20 20 20 69 6e 63 72 20 69 44  sql].    incr iD
0440: 65 70 74 68 20 2d 31 0a 20 20 7d 0a 20 20 0a 20  epth -1.  }.  . 
0450: 20 72 65 74 75 72 6e 20 24 69 44 65 70 74 68 0a   return $iDepth.
0460: 7d 0a 0a 23 20 52 65 74 75 72 6e 20 74 68 65 20  }..# Return the 
0470: 6e 75 6d 62 65 72 20 6f 66 20 64 69 6d 65 6e 73  number of dimens
0480: 69 6f 6e 73 20 6f 66 20 74 68 65 20 72 74 72 65  ions of the rtre
0490: 65 2e 0a 23 0a 70 72 6f 63 20 72 74 72 65 65 5f  e..#.proc rtree_
04a0: 6e 64 69 6d 20 7b 64 62 20 7a 54 61 62 7d 20 7b  ndim {db zTab} {
04b0: 0a 20 20 73 65 74 20 6e 44 69 6d 20 5b 65 78 70  .  set nDim [exp
04c0: 72 20 7b 28 28 5b 6c 6c 65 6e 67 74 68 20 5b 24  r {(([llength [$
04d0: 64 62 20 65 76 61 6c 20 22 70 72 61 67 6d 61 20  db eval "pragma 
04e0: 74 61 62 6c 65 5f 69 6e 66 6f 28 24 7a 54 61 62  table_info($zTab
04f0: 29 22 5d 5d 2f 36 29 2d 31 29 2f 32 7d 5d 0a 7d  )"]]/6)-1)/2}].}
0500: 0a 0a 23 20 52 65 74 75 72 6e 20 74 68 65 20 63  ..# Return the c
0510: 6f 6e 74 65 6e 74 73 20 6f 66 20 72 74 72 65 65  ontents of rtree
0520: 20 6e 6f 64 65 20 24 69 4e 6f 64 65 2e 0a 23 0a   node $iNode..#.
0530: 70 72 6f 63 20 72 74 72 65 65 5f 6e 6f 64 65 20  proc rtree_node 
0540: 7b 64 62 20 7a 54 61 62 20 69 4e 6f 64 65 20 7b  {db zTab iNode {
0550: 69 50 72 65 63 20 36 7d 7d 20 7b 0a 20 20 73 65  iPrec 6}} {.  se
0560: 74 20 6e 44 69 6d 20 5b 72 74 72 65 65 5f 6e 64  t nDim [rtree_nd
0570: 69 6d 20 24 64 62 20 24 7a 54 61 62 5d 0a 20 20  im $db $zTab].  
0580: 73 65 74 20 73 71 6c 20 22 0a 20 20 20 20 53 45  set sql ".    SE
0590: 4c 45 43 54 20 72 74 72 65 65 6e 6f 64 65 28 24  LECT rtreenode($
05a0: 6e 44 69 6d 2c 20 64 61 74 61 29 20 46 52 4f 4d  nDim, data) FROM
05b0: 20 24 7b 7a 54 61 62 7d 5f 6e 6f 64 65 20 57 48   ${zTab}_node WH
05c0: 45 52 45 20 6e 6f 64 65 6e 6f 20 3d 20 24 69 4e  ERE nodeno = $iN
05d0: 6f 64 65 0a 20 20 22 0a 20 20 73 65 74 20 6e 6f  ode.  ".  set no
05e0: 64 65 20 5b 64 62 20 6f 6e 65 20 24 73 71 6c 5d  de [db one $sql]
05f0: 0a 0a 20 20 73 65 74 20 6e 43 65 6c 6c 20 5b 6c  ..  set nCell [l
0600: 6c 65 6e 67 74 68 20 24 6e 6f 64 65 5d 0a 20 20  length $node].  
0610: 73 65 74 20 6e 43 6f 6f 72 64 20 5b 65 78 70 72  set nCoord [expr
0620: 20 24 6e 44 69 6d 2a 32 5d 0a 20 20 66 6f 72 20   $nDim*2].  for 
0630: 7b 73 65 74 20 69 69 20 30 7d 20 7b 24 69 69 20  {set ii 0} {$ii 
0640: 3c 20 24 6e 43 65 6c 6c 7d 20 7b 69 6e 63 72 20  < $nCell} {incr 
0650: 69 69 7d 20 7b 0a 20 20 20 20 66 6f 72 20 7b 73  ii} {.    for {s
0660: 65 74 20 6a 6a 20 31 7d 20 7b 24 6a 6a 20 3c 3d  et jj 1} {$jj <=
0670: 20 24 6e 43 6f 6f 72 64 7d 20 7b 69 6e 63 72 20   $nCoord} {incr 
0680: 6a 6a 7d 20 7b 0a 20 20 20 20 20 20 73 65 74 20  jj} {.      set 
0690: 6e 65 77 76 61 6c 20 5b 66 6f 72 6d 61 74 20 22  newval [format "
06a0: 25 2e 24 7b 69 50 72 65 63 7d 66 22 20 5b 6c 69  %.${iPrec}f" [li
06b0: 6e 64 65 78 20 24 6e 6f 64 65 20 24 69 69 20 24  ndex $node $ii $
06c0: 6a 6a 5d 5d 0a 20 20 20 20 20 20 6c 73 65 74 20  jj]].      lset 
06d0: 6e 6f 64 65 20 24 69 69 20 24 6a 6a 20 24 6e 65  node $ii $jj $ne
06e0: 77 76 61 6c 0a 20 20 20 20 7d 0a 20 20 7d 0a 20  wval.    }.  }. 
06f0: 20 73 65 74 20 6e 6f 64 65 0a 7d 0a 0a 70 72 6f   set node.}..pro
0700: 63 20 72 74 72 65 65 5f 6d 69 6e 63 65 6c 6c 73  c rtree_mincells
0710: 20 7b 64 62 20 7a 54 61 62 7d 20 7b 0a 20 20 73   {db zTab} {.  s
0720: 65 74 20 6e 20 5b 24 64 62 20 6f 6e 65 20 22 73  et n [$db one "s
0730: 65 6c 65 63 74 20 6c 65 6e 67 74 68 28 64 61 74  elect length(dat
0740: 61 29 20 46 52 4f 4d 20 24 7b 7a 54 61 62 7d 5f  a) FROM ${zTab}_
0750: 6e 6f 64 65 20 4c 49 4d 49 54 20 31 22 5d 0a 20  node LIMIT 1"]. 
0760: 20 73 65 74 20 6e 4d 61 78 20 5b 65 78 70 72 20   set nMax [expr 
0770: 7b 69 6e 74 28 28 24 6e 2d 34 29 2f 28 38 2b 5b  {int(($n-4)/(8+[
0780: 72 74 72 65 65 5f 6e 64 69 6d 20 24 64 62 20 24  rtree_ndim $db $
0790: 7a 54 61 62 5d 2a 32 2a 34 29 29 7d 5d 0a 20 20  zTab]*2*4))}].  
07a0: 72 65 74 75 72 6e 20 5b 65 78 70 72 20 7b 69 6e  return [expr {in
07b0: 74 28 24 6e 4d 61 78 2f 33 29 7d 5d 0a 7d 0a 0a  t($nMax/3)}].}..
07c0: 23 20 41 6e 20 69 6e 74 65 67 72 69 74 79 20 63  # An integrity c
07d0: 68 65 63 6b 20 66 6f 72 20 74 68 65 20 72 74 72  heck for the rtr
07e0: 65 65 20 24 7a 54 61 62 20 61 63 63 65 73 73 69  ee $zTab accessi
07f0: 62 6c 65 20 76 69 61 20 64 61 74 61 62 61 73 65  ble via database
0800: 20 0a 23 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 24   .# connection $
0810: 64 62 2e 0a 23 0a 70 72 6f 63 20 72 74 72 65 65  db..#.proc rtree
0820: 5f 63 68 65 63 6b 20 7b 64 62 20 7a 54 61 62 7d  _check {db zTab}
0830: 20 7b 0a 20 20 61 72 72 61 79 20 75 6e 73 65 74   {.  array unset
0840: 20 3a 3a 63 68 65 63 6b 65 64 0a 20 0a 20 20 23   ::checked. .  #
0850: 20 43 68 65 63 6b 20 65 61 63 68 20 72 2d 74 72   Check each r-tr
0860: 65 65 20 6e 6f 64 65 2e 0a 20 20 73 65 74 20 72  ee node..  set r
0870: 63 20 5b 63 61 74 63 68 20 7b 0a 20 20 20 20 72  c [catch {.    r
0880: 74 72 65 65 5f 6e 6f 64 65 5f 63 68 65 63 6b 20  tree_node_check 
0890: 24 64 62 20 24 7a 54 61 62 20 31 20 5b 72 74 72  $db $zTab 1 [rtr
08a0: 65 65 5f 64 65 70 74 68 20 24 64 62 20 24 7a 54  ee_depth $db $zT
08b0: 61 62 5d 0a 20 20 7d 20 6d 73 67 5d 0a 20 20 69  ab].  } msg].  i
08c0: 66 20 7b 24 72 63 20 26 26 20 24 6d 73 67 20 6e  f {$rc && $msg n
08d0: 65 20 22 22 7d 20 7b 20 65 72 72 6f 72 20 24 6d  e ""} { error $m
08e0: 73 67 20 7d 0a 0a 20 20 23 20 43 68 65 63 6b 20  sg }..  # Check 
08f0: 74 68 61 74 20 74 68 65 20 5f 72 6f 77 69 64 20  that the _rowid 
0900: 61 6e 64 20 5f 70 61 72 65 6e 74 20 74 61 62 6c  and _parent tabl
0910: 65 73 20 68 61 76 65 20 74 68 65 20 72 69 67 68  es have the righ
0920: 74 20 0a 20 20 23 20 6e 75 6d 62 65 72 20 6f 66  t .  # number of
0930: 20 65 6e 74 72 69 65 73 2e 0a 20 20 73 65 74 20   entries..  set 
0940: 6e 4e 6f 64 65 20 20 20 5b 24 64 62 20 6f 6e 65  nNode   [$db one
0950: 20 22 53 45 4c 45 43 54 20 63 6f 75 6e 74 28 2a   "SELECT count(*
0960: 29 20 46 52 4f 4d 20 24 7b 7a 54 61 62 7d 5f 6e  ) FROM ${zTab}_n
0970: 6f 64 65 22 5d 0a 20 20 73 65 74 20 6e 52 6f 77  ode"].  set nRow
0980: 20 20 20 20 5b 24 64 62 20 6f 6e 65 20 22 53 45      [$db one "SE
0990: 4c 45 43 54 20 63 6f 75 6e 74 28 2a 29 20 46 52  LECT count(*) FR
09a0: 4f 4d 20 24 7b 7a 54 61 62 7d 22 5d 0a 20 20 73  OM ${zTab}"].  s
09b0: 65 74 20 6e 52 6f 77 69 64 20 20 5b 24 64 62 20  et nRowid  [$db 
09c0: 6f 6e 65 20 22 53 45 4c 45 43 54 20 63 6f 75 6e  one "SELECT coun
09d0: 74 28 2a 29 20 46 52 4f 4d 20 24 7b 7a 54 61 62  t(*) FROM ${zTab
09e0: 7d 5f 72 6f 77 69 64 22 5d 0a 20 20 73 65 74 20  }_rowid"].  set 
09f0: 6e 50 61 72 65 6e 74 20 5b 24 64 62 20 6f 6e 65  nParent [$db one
0a00: 20 22 53 45 4c 45 43 54 20 63 6f 75 6e 74 28 2a   "SELECT count(*
0a10: 29 20 46 52 4f 4d 20 24 7b 7a 54 61 62 7d 5f 70  ) FROM ${zTab}_p
0a20: 61 72 65 6e 74 22 5d 0a 0a 20 20 69 66 20 7b 24  arent"]..  if {$
0a30: 6e 4e 6f 64 65 20 21 3d 20 28 24 6e 50 61 72 65  nNode != ($nPare
0a40: 6e 74 2b 31 29 7d 20 7b 20 0a 20 20 20 20 65 72  nt+1)} { .    er
0a50: 72 6f 72 20 22 57 72 6f 6e 67 20 6e 75 6d 62 65  ror "Wrong numbe
0a60: 72 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20  r of entries in 
0a70: 24 7b 7a 54 61 62 7d 5f 70 61 72 65 6e 74 22 0a  ${zTab}_parent".
0a80: 20 20 7d 0a 20 20 69 66 20 7b 24 6e 52 6f 77 20    }.  if {$nRow 
0a90: 21 3d 20 24 6e 52 6f 77 69 64 7d 20 7b 20 0a 20  != $nRowid} { . 
0aa0: 20 20 20 65 72 72 6f 72 20 22 57 72 6f 6e 67 20     error "Wrong 
0ab0: 6e 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65  number of entrie
0ac0: 73 20 69 6e 20 24 7b 7a 54 61 62 7d 5f 72 6f 77  s in ${zTab}_row
0ad0: 69 64 22 0a 20 20 7d 0a 20 20 0a 20 20 72 65 74  id".  }.  .  ret
0ae0: 75 72 6e 20 24 72 63 0a 7d 0a 0a 70 72 6f 63 20  urn $rc.}..proc 
0af0: 72 74 72 65 65 5f 6e 6f 64 65 5f 63 68 65 63 6b  rtree_node_check
0b00: 20 7b 64 62 20 7a 54 61 62 20 69 4e 6f 64 65 20   {db zTab iNode 
0b10: 69 44 65 70 74 68 7d 20 7b 0a 20 20 69 66 20 7b  iDepth} {.  if {
0b20: 5b 69 6e 66 6f 20 65 78 69 73 74 73 20 3a 3a 63  [info exists ::c
0b30: 68 65 63 6b 65 64 28 24 69 4e 6f 64 65 29 5d 7d  hecked($iNode)]}
0b40: 20 7b 20 65 72 72 6f 72 20 22 53 65 63 6f 6e 64   { error "Second
0b50: 20 72 65 66 20 74 6f 20 24 69 4e 6f 64 65 22 20   ref to $iNode" 
0b60: 7d 0a 20 20 73 65 74 20 3a 3a 63 68 65 63 6b 65  }.  set ::checke
0b70: 64 28 24 69 4e 6f 64 65 29 20 31 0a 0a 20 20 73  d($iNode) 1..  s
0b80: 65 74 20 6e 6f 64 65 20 5b 72 74 72 65 65 5f 6e  et node [rtree_n
0b90: 6f 64 65 20 24 64 62 20 24 7a 54 61 62 20 24 69  ode $db $zTab $i
0ba0: 4e 6f 64 65 5d 0a 20 20 69 66 20 7b 24 69 4e 6f  Node].  if {$iNo
0bb0: 64 65 21 3d 31 20 26 26 20 5b 6c 6c 65 6e 67 74  de!=1 && [llengt
0bc0: 68 20 24 6e 6f 64 65 5d 3d 3d 30 7d 20 7b 20 65  h $node]==0} { e
0bd0: 72 72 6f 72 20 22 4e 6f 20 73 75 63 68 20 6e 6f  rror "No such no
0be0: 64 65 3a 20 24 69 4e 6f 64 65 22 20 7d 0a 0a 20  de: $iNode" }.. 
0bf0: 20 69 66 20 7b 24 69 4e 6f 64 65 20 21 3d 20 31   if {$iNode != 1
0c00: 20 26 26 20 5b 6c 6c 65 6e 67 74 68 20 24 6e 6f   && [llength $no
0c10: 64 65 5d 3c 5b 72 74 72 65 65 5f 6d 69 6e 63 65  de]<[rtree_mince
0c20: 6c 6c 73 20 24 64 62 20 24 7a 54 61 62 5d 7d 20  lls $db $zTab]} 
0c30: 7b 0a 20 20 20 20 70 75 74 73 20 22 4e 6f 64 65  {.    puts "Node
0c40: 20 24 69 4e 6f 64 65 3a 20 48 61 73 20 6f 6e 6c   $iNode: Has onl
0c50: 79 20 5b 6c 6c 65 6e 67 74 68 20 24 6e 6f 64 65  y [llength $node
0c60: 5d 20 63 65 6c 6c 73 22 0a 20 20 20 20 65 72 72  ] cells".    err
0c70: 6f 72 20 22 22 0a 20 20 7d 0a 20 20 69 66 20 7b  or "".  }.  if {
0c80: 24 69 4e 6f 64 65 20 3d 3d 20 31 20 26 26 20 5b  $iNode == 1 && [
0c90: 6c 6c 65 6e 67 74 68 20 24 6e 6f 64 65 5d 3d 3d  llength $node]==
0ca0: 31 20 26 26 20 5b 72 74 72 65 65 5f 64 65 70 74  1 && [rtree_dept
0cb0: 68 20 24 64 62 20 24 7a 54 61 62 5d 3e 30 7d 20  h $db $zTab]>0} 
0cc0: 7b 0a 20 20 20 20 73 65 74 20 64 65 70 74 68 20  {.    set depth 
0cd0: 5b 72 74 72 65 65 5f 64 65 70 74 68 20 24 64 62  [rtree_depth $db
0ce0: 20 24 7a 54 61 62 5d 0a 20 20 20 20 70 75 74 73   $zTab].    puts
0cf0: 20 22 4e 6f 64 65 20 24 69 4e 6f 64 65 3a 20 48   "Node $iNode: H
0d00: 61 73 20 6f 6e 6c 79 20 31 20 63 68 69 6c 64 20  as only 1 child 
0d10: 28 74 72 65 65 20 64 65 70 74 68 20 69 73 20 24  (tree depth is $
0d20: 64 65 70 74 68 29 22 0a 20 20 20 20 65 72 72 6f  depth)".    erro
0d30: 72 20 22 22 0a 20 20 7d 0a 0a 20 20 73 65 74 20  r "".  }..  set 
0d40: 6e 44 69 6d 20 5b 65 78 70 72 20 7b 28 5b 6c 6c  nDim [expr {([ll
0d50: 65 6e 67 74 68 20 5b 6c 69 6e 64 65 78 20 24 6e  ength [lindex $n
0d60: 6f 64 65 20 30 5d 5d 2d 31 29 2f 32 7d 5d 0a 0a  ode 0]]-1)/2}]..
0d70: 20 20 69 66 20 7b 24 69 44 65 70 74 68 20 3e 20    if {$iDepth > 
0d80: 30 7d 20 7b 0a 20 20 20 20 73 65 74 20 64 20 5b  0} {.    set d [
0d90: 65 78 70 72 20 24 69 44 65 70 74 68 2d 31 5d 0a  expr $iDepth-1].
0da0: 20 20 20 20 66 6f 72 65 61 63 68 20 63 65 6c 6c      foreach cell
0db0: 20 24 6e 6f 64 65 20 7b 0a 20 20 20 20 20 20 73   $node {.      s
0dc0: 65 74 20 73 68 6f 75 6c 64 62 65 20 5b 72 74 72  et shouldbe [rtr
0dd0: 65 65 5f 6e 6f 64 65 5f 63 68 65 63 6b 20 24 64  ee_node_check $d
0de0: 62 20 24 7a 54 61 62 20 5b 6c 69 6e 64 65 78 20  b $zTab [lindex 
0df0: 24 63 65 6c 6c 20 30 5d 20 24 64 5d 0a 20 20 20  $cell 0] $d].   
0e00: 20 20 20 69 66 20 7b 24 63 65 6c 6c 20 6e 65 20     if {$cell ne 
0e10: 24 73 68 6f 75 6c 64 62 65 7d 20 7b 0a 20 20 20  $shouldbe} {.   
0e20: 20 20 20 20 20 70 75 74 73 20 22 4e 6f 64 65 20       puts "Node 
0e30: 24 69 4e 6f 64 65 3a 20 43 65 6c 6c 20 69 73 3a  $iNode: Cell is:
0e40: 20 7b 24 63 65 6c 6c 7d 2c 20 73 68 6f 75 6c 64   {$cell}, should
0e50: 20 62 65 20 7b 24 73 68 6f 75 6c 64 62 65 7d 22   be {$shouldbe}"
0e60: 0a 20 20 20 20 20 20 20 20 65 72 72 6f 72 20 22  .        error "
0e70: 22 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a  ".      }.    }.
0e80: 20 20 7d 0a 0a 20 20 73 65 74 20 6d 61 70 70 69    }..  set mappi
0e90: 6e 67 5f 74 61 62 6c 65 20 22 24 7b 7a 54 61 62  ng_table "${zTab
0ea0: 7d 5f 70 61 72 65 6e 74 22 20 0a 20 20 73 65 74  }_parent" .  set
0eb0: 20 6d 61 70 70 69 6e 67 5f 73 71 6c 20 22 53 45   mapping_sql "SE
0ec0: 4c 45 43 54 20 70 61 72 65 6e 74 6e 6f 64 65 20  LECT parentnode 
0ed0: 46 52 4f 4d 20 24 6d 61 70 70 69 6e 67 5f 74 61  FROM $mapping_ta
0ee0: 62 6c 65 20 57 48 45 52 45 20 72 6f 77 69 64 20  ble WHERE rowid 
0ef0: 3d 20 5c 24 72 6f 77 69 64 22 0a 20 20 69 66 20  = \$rowid".  if 
0f00: 7b 24 69 44 65 70 74 68 3d 3d 30 7d 20 7b 20 0a  {$iDepth==0} { .
0f10: 20 20 20 20 73 65 74 20 6d 61 70 70 69 6e 67 5f      set mapping_
0f20: 74 61 62 6c 65 20 22 24 7b 7a 54 61 62 7d 5f 72  table "${zTab}_r
0f30: 6f 77 69 64 22 0a 20 20 20 20 73 65 74 20 6d 61  owid".    set ma
0f40: 70 70 69 6e 67 5f 73 71 6c 20 22 53 45 4c 45 43  pping_sql "SELEC
0f50: 54 20 6e 6f 64 65 6e 6f 20 46 52 4f 4d 20 24 6d  T nodeno FROM $m
0f60: 61 70 70 69 6e 67 5f 74 61 62 6c 65 20 57 48 45  apping_table WHE
0f70: 52 45 20 72 6f 77 69 64 20 3d 20 5c 24 72 6f 77  RE rowid = \$row
0f80: 69 64 22 0a 20 20 7d 0a 20 20 66 6f 72 65 61 63  id".  }.  foreac
0f90: 68 20 63 65 6c 6c 20 24 6e 6f 64 65 20 7b 0a 20  h cell $node {. 
0fa0: 20 20 20 73 65 74 20 72 6f 77 69 64 20 5b 6c 69     set rowid [li
0fb0: 6e 64 65 78 20 24 63 65 6c 6c 20 30 5d 0a 20 20  ndex $cell 0].  
0fc0: 20 20 73 65 74 20 6d 61 70 70 69 6e 67 20 5b 64    set mapping [d
0fd0: 62 20 6f 6e 65 20 24 6d 61 70 70 69 6e 67 5f 73  b one $mapping_s
0fe0: 71 6c 5d 0a 20 20 20 20 69 66 20 7b 24 6d 61 70  ql].    if {$map
0ff0: 70 69 6e 67 20 21 3d 20 24 69 4e 6f 64 65 7d 20  ping != $iNode} 
1000: 7b 0a 20 20 20 20 20 20 70 75 74 73 20 22 4e 6f  {.      puts "No
1010: 64 65 20 24 69 4e 6f 64 65 3a 20 24 6d 61 70 70  de $iNode: $mapp
1020: 69 6e 67 5f 74 61 62 6c 65 20 65 6e 74 72 79 20  ing_table entry 
1030: 66 6f 72 20 63 65 6c 6c 20 24 72 6f 77 69 64 20  for cell $rowid 
1040: 69 73 20 24 6d 61 70 70 69 6e 67 22 0a 20 20 20  is $mapping".   
1050: 20 20 20 65 72 72 6f 72 20 22 22 0a 20 20 20 20     error "".    
1060: 7d 0a 20 20 7d 0a 0a 20 20 73 65 74 20 72 65 74  }.  }..  set ret
1070: 20 5b 6c 69 73 74 20 24 69 4e 6f 64 65 5d 0a 20   [list $iNode]. 
1080: 20 66 6f 72 20 7b 73 65 74 20 69 69 20 31 7d 20   for {set ii 1} 
1090: 7b 24 69 69 20 3c 3d 20 24 6e 44 69 6d 2a 32 7d  {$ii <= $nDim*2}
10a0: 20 7b 69 6e 63 72 20 69 69 7d 20 7b 0a 20 20 20   {incr ii} {.   
10b0: 20 73 65 74 20 66 20 5b 6c 69 6e 64 65 78 20 24   set f [lindex $
10c0: 6e 6f 64 65 20 30 20 24 69 69 5d 0a 20 20 20 20  node 0 $ii].    
10d0: 66 6f 72 65 61 63 68 20 63 65 6c 6c 20 24 6e 6f  foreach cell $no
10e0: 64 65 20 7b 0a 20 20 20 20 20 20 73 65 74 20 66  de {.      set f
10f0: 32 20 5b 6c 69 6e 64 65 78 20 24 63 65 6c 6c 20  2 [lindex $cell 
1100: 24 69 69 5d 0a 20 20 20 20 20 20 69 66 20 7b 28  $ii].      if {(
1110: 24 69 69 25 32 29 3d 3d 31 20 26 26 20 24 66 32  $ii%2)==1 && $f2
1120: 3c 24 66 7d 20 7b 73 65 74 20 66 20 24 66 32 7d  <$f} {set f $f2}
1130: 0a 20 20 20 20 20 20 69 66 20 7b 28 24 69 69 25  .      if {($ii%
1140: 32 29 3d 3d 30 20 26 26 20 24 66 32 3e 24 66 7d  2)==0 && $f2>$f}
1150: 20 7b 73 65 74 20 66 20 24 66 32 7d 0a 20 20 20   {set f $f2}.   
1160: 20 7d 0a 20 20 20 20 6c 61 70 70 65 6e 64 20 72   }.    lappend r
1170: 65 74 20 24 66 0a 20 20 7d 0a 20 20 72 65 74 75  et $f.  }.  retu
1180: 72 6e 20 24 72 65 74 0a 7d 0a 0a 70 72 6f 63 20  rn $ret.}..proc 
1190: 72 74 72 65 65 5f 64 75 6d 70 20 7b 64 62 20 7a  rtree_dump {db z
11a0: 54 61 62 7d 20 7b 0a 20 20 73 65 74 20 7a 52 65  Tab} {.  set zRe
11b0: 74 20 22 22 0a 20 20 73 65 74 20 6e 44 69 6d 20  t "".  set nDim 
11c0: 5b 65 78 70 72 20 7b 28 28 5b 6c 6c 65 6e 67 74  [expr {(([llengt
11d0: 68 20 5b 24 64 62 20 65 76 61 6c 20 22 70 72 61  h [$db eval "pra
11e0: 67 6d 61 20 74 61 62 6c 65 5f 69 6e 66 6f 28 24  gma table_info($
11f0: 7a 54 61 62 29 22 5d 5d 2f 36 29 2d 31 29 2f 32  zTab)"]]/6)-1)/2
1200: 7d 5d 0a 20 20 73 65 74 20 73 71 6c 20 22 53 45  }].  set sql "SE
1210: 4c 45 43 54 20 6e 6f 64 65 6e 6f 2c 20 72 74 72  LECT nodeno, rtr
1220: 65 65 6e 6f 64 65 28 24 6e 44 69 6d 2c 20 64 61  eenode($nDim, da
1230: 74 61 29 20 41 53 20 6e 6f 64 65 20 46 52 4f 4d  ta) AS node FROM
1240: 20 24 7b 7a 54 61 62 7d 5f 6e 6f 64 65 22 0a 20   ${zTab}_node". 
1250: 20 24 64 62 20 65 76 61 6c 20 24 73 71 6c 20 7b   $db eval $sql {
1260: 0a 20 20 20 20 61 70 70 65 6e 64 20 7a 52 65 74  .    append zRet
1270: 20 5b 66 6f 72 6d 61 74 20 22 25 20 2d 31 30 73   [format "% -10s
1280: 20 25 73 5c 6e 22 20 24 6e 6f 64 65 6e 6f 20 24   %s\n" $nodeno $
1290: 6e 6f 64 65 5d 0a 20 20 7d 0a 20 20 73 65 74 20  node].  }.  set 
12a0: 7a 52 65 74 0a 7d 0a 0a 70 72 6f 63 20 72 74 72  zRet.}..proc rtr
12b0: 65 65 5f 6e 6f 64 65 74 72 65 65 64 75 6d 70 20  ee_nodetreedump 
12c0: 7b 64 62 20 7a 54 61 62 20 7a 49 6e 64 65 6e 74  {db zTab zIndent
12d0: 20 69 44 65 70 74 68 20 69 4e 6f 64 65 7d 20 7b   iDepth iNode} {
12e0: 0a 20 20 73 65 74 20 72 65 74 20 22 22 0a 20 20  .  set ret "".  
12f0: 73 65 74 20 6e 6f 64 65 20 5b 72 74 72 65 65 5f  set node [rtree_
1300: 6e 6f 64 65 20 24 64 62 20 24 7a 54 61 62 20 24  node $db $zTab $
1310: 69 4e 6f 64 65 20 31 5d 0a 20 20 61 70 70 65 6e  iNode 1].  appen
1320: 64 20 72 65 74 20 5b 66 6f 72 6d 61 74 20 22 25  d ret [format "%
1330: 2d 33 64 20 25 73 25 73 5c 6e 22 20 24 69 4e 6f  -3d %s%s\n" $iNo
1340: 64 65 20 24 7a 49 6e 64 65 6e 74 20 24 6e 6f 64  de $zIndent $nod
1350: 65 5d 0a 20 20 69 66 20 7b 24 69 44 65 70 74 68  e].  if {$iDepth
1360: 3e 30 7d 20 7b 0a 20 20 20 20 66 6f 72 65 61 63  >0} {.    foreac
1370: 68 20 63 65 6c 6c 20 24 6e 6f 64 65 20 7b 0a 20  h cell $node {. 
1380: 20 20 20 20 20 73 65 74 20 69 20 5b 6c 69 6e 64       set i [lind
1390: 65 78 20 24 63 65 6c 6c 20 30 5d 0a 20 20 20 20  ex $cell 0].    
13a0: 20 20 61 70 70 65 6e 64 20 72 65 74 20 5b 72 74    append ret [rt
13b0: 72 65 65 5f 6e 6f 64 65 74 72 65 65 64 75 6d 70  ree_nodetreedump
13c0: 20 24 64 62 20 24 7a 54 61 62 20 22 24 7a 49 6e   $db $zTab "$zIn
13d0: 64 65 6e 74 20 20 22 20 5b 65 78 70 72 20 24 69  dent  " [expr $i
13e0: 44 65 70 74 68 2d 31 5d 20 24 69 5d 0a 20 20 20  Depth-1] $i].   
13f0: 20 7d 0a 20 20 7d 0a 20 20 73 65 74 20 72 65 74   }.  }.  set ret
1400: 0a 7d 0a 0a 70 72 6f 63 20 72 74 72 65 65 5f 74  .}..proc rtree_t
1410: 72 65 65 64 75 6d 70 20 7b 64 62 20 7a 54 61 62  reedump {db zTab
1420: 7d 20 7b 0a 20 20 73 65 74 20 64 20 5b 72 74 72  } {.  set d [rtr
1430: 65 65 5f 64 65 70 74 68 20 24 64 62 20 24 7a 54  ee_depth $db $zT
1440: 61 62 5d 0a 20 20 72 74 72 65 65 5f 6e 6f 64 65  ab].  rtree_node
1450: 74 72 65 65 64 75 6d 70 20 24 64 62 20 24 7a 54  treedump $db $zT
1460: 61 62 20 22 22 20 24 64 20 31 0a 7d 0a 0a 70 72  ab "" $d 1.}..pr
1470: 6f 63 20 64 6f 5f 72 74 72 65 65 5f 69 6e 74 65  oc do_rtree_inte
1480: 67 72 69 74 79 5f 74 65 73 74 20 7b 74 6e 20 74  grity_test {tn t
1490: 62 6c 7d 20 7b 0a 20 20 75 70 6c 65 76 65 6c 20  bl} {.  uplevel 
14a0: 5b 6c 69 73 74 20 64 6f 5f 65 78 65 63 73 71 6c  [list do_execsql
14b0: 5f 74 65 73 74 20 24 74 6e 20 22 53 45 4c 45 43  _test $tn "SELEC
14c0: 54 20 72 74 72 65 65 63 68 65 63 6b 28 27 24 74  T rtreecheck('$t
14d0: 62 6c 27 29 22 20 6f 6b 5d 0a 7d 0a 0a           bl')" ok].}..