/ Hex Artifact Content
Login

Artifact ee0a0311eb12175319d78bfb37302320496cee6e:


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 23 20 24 49 64 3a 20 72  tion..#.# $Id: r
0230: 74 72 65 65 5f 75 74 69 6c 2e 74 63 6c 2c 76 20  tree_util.tcl,v 
0240: 31 2e 31 20 32 30 30 38 2f 30 35 2f 32 36 20 31  1.1 2008/05/26 1
0250: 38 3a 34 31 3a 35 34 20 64 61 6e 69 65 6c 6b 31  8:41:54 danielk1
0260: 39 37 37 20 45 78 70 20 24 0a 23 0a 0a 0a 23 2d  977 Exp $.#...#-
0270: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0280: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0290: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
02a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
02b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 23 20 50 55 42 4c  ---------.# PUBL
02c0: 49 43 20 41 50 49 3a 0a 23 0a 23 20 20 20 72 74  IC API:.#.#   rt
02d0: 72 65 65 5f 64 65 70 74 68 0a 23 20 20 20 72 74  ree_depth.#   rt
02e0: 72 65 65 5f 6e 64 69 6d 0a 23 20 20 20 72 74 72  ree_ndim.#   rtr
02f0: 65 65 5f 6e 6f 64 65 0a 23 20 20 20 72 74 72 65  ee_node.#   rtre
0300: 65 5f 6d 69 6e 63 65 6c 6c 73 0a 23 20 20 20 72  e_mincells.#   r
0310: 74 72 65 65 5f 63 68 65 63 6b 0a 23 20 20 20 72  tree_check.#   r
0320: 74 72 65 65 5f 64 75 6d 70 0a 23 20 20 20 72 74  tree_dump.#   rt
0330: 72 65 65 5f 74 72 65 65 64 75 6d 70 0a 23 0a 0a  ree_treedump.#..
0340: 70 72 6f 63 20 72 74 72 65 65 5f 64 65 70 74 68  proc rtree_depth
0350: 20 7b 64 62 20 7a 54 61 62 7d 20 7b 0a 20 20 24   {db zTab} {.  $
0360: 64 62 20 6f 6e 65 20 22 53 45 4c 45 43 54 20 72  db one "SELECT r
0370: 74 72 65 65 64 65 70 74 68 28 64 61 74 61 29 20  treedepth(data) 
0380: 46 52 4f 4d 20 24 7b 7a 54 61 62 7d 5f 6e 6f 64  FROM ${zTab}_nod
0390: 65 20 57 48 45 52 45 20 6e 6f 64 65 6e 6f 3d 31  e WHERE nodeno=1
03a0: 22 0a 7d 0a 0a 70 72 6f 63 20 72 74 72 65 65 5f  ".}..proc rtree_
03b0: 6e 6f 64 65 64 65 70 74 68 20 7b 64 62 20 7a 54  nodedepth {db zT
03c0: 61 62 20 69 4e 6f 64 65 7d 20 7b 0a 20 20 73 65  ab iNode} {.  se
03d0: 74 20 69 44 65 70 74 68 20 5b 72 74 72 65 65 5f  t iDepth [rtree_
03e0: 64 65 70 74 68 20 24 64 62 20 24 7a 54 61 62 5d  depth $db $zTab]
03f0: 0a 20 20 0a 20 20 73 65 74 20 69 69 20 24 69 4e  .  .  set ii $iN
0400: 6f 64 65 0a 20 20 77 68 69 6c 65 20 7b 24 69 69  ode.  while {$ii
0410: 20 21 3d 20 31 7d 20 7b 0a 20 20 20 20 73 65 74   != 1} {.    set
0420: 20 73 71 6c 20 22 53 45 4c 45 43 54 20 70 61 72   sql "SELECT par
0430: 65 6e 74 6e 6f 64 65 20 46 52 4f 4d 20 24 7b 7a  entnode FROM ${z
0440: 54 61 62 7d 5f 70 61 72 65 6e 74 20 57 48 45 52  Tab}_parent WHER
0450: 45 20 6e 6f 64 65 6e 6f 20 3d 20 24 69 69 22 0a  E nodeno = $ii".
0460: 20 20 20 20 73 65 74 20 69 69 20 5b 64 62 20 6f      set ii [db o
0470: 6e 65 20 24 73 71 6c 5d 0a 20 20 20 20 69 6e 63  ne $sql].    inc
0480: 72 20 69 44 65 70 74 68 20 2d 31 0a 20 20 7d 0a  r iDepth -1.  }.
0490: 20 20 0a 20 20 72 65 74 75 72 6e 20 24 69 44 65    .  return $iDe
04a0: 70 74 68 0a 7d 0a 0a 23 20 52 65 74 75 72 6e 20  pth.}..# Return 
04b0: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 64 69  the number of di
04c0: 6d 65 6e 73 69 6f 6e 73 20 6f 66 20 74 68 65 20  mensions of the 
04d0: 72 74 72 65 65 2e 0a 23 0a 70 72 6f 63 20 72 74  rtree..#.proc rt
04e0: 72 65 65 5f 6e 64 69 6d 20 7b 64 62 20 7a 54 61  ree_ndim {db zTa
04f0: 62 7d 20 7b 0a 20 20 73 65 74 20 6e 44 69 6d 20  b} {.  set nDim 
0500: 5b 65 78 70 72 20 7b 28 28 5b 6c 6c 65 6e 67 74  [expr {(([llengt
0510: 68 20 5b 24 64 62 20 65 76 61 6c 20 22 70 72 61  h [$db eval "pra
0520: 67 6d 61 20 74 61 62 6c 65 5f 69 6e 66 6f 28 24  gma table_info($
0530: 7a 54 61 62 29 22 5d 5d 2f 36 29 2d 31 29 2f 32  zTab)"]]/6)-1)/2
0540: 7d 5d 0a 7d 0a 0a 23 20 52 65 74 75 72 6e 20 74  }].}..# Return t
0550: 68 65 20 63 6f 6e 74 65 6e 74 73 20 6f 66 20 72  he contents of r
0560: 74 72 65 65 20 6e 6f 64 65 20 24 69 4e 6f 64 65  tree node $iNode
0570: 2e 0a 23 0a 70 72 6f 63 20 72 74 72 65 65 5f 6e  ..#.proc rtree_n
0580: 6f 64 65 20 7b 64 62 20 7a 54 61 62 20 69 4e 6f  ode {db zTab iNo
0590: 64 65 20 7b 69 50 72 65 63 20 36 7d 7d 20 7b 0a  de {iPrec 6}} {.
05a0: 20 20 73 65 74 20 6e 44 69 6d 20 5b 72 74 72 65    set nDim [rtre
05b0: 65 5f 6e 64 69 6d 20 24 64 62 20 24 7a 54 61 62  e_ndim $db $zTab
05c0: 5d 0a 20 20 73 65 74 20 73 71 6c 20 22 0a 20 20  ].  set sql ".  
05d0: 20 20 53 45 4c 45 43 54 20 72 74 72 65 65 6e 6f    SELECT rtreeno
05e0: 64 65 28 24 6e 44 69 6d 2c 20 64 61 74 61 29 20  de($nDim, data) 
05f0: 46 52 4f 4d 20 24 7b 7a 54 61 62 7d 5f 6e 6f 64  FROM ${zTab}_nod
0600: 65 20 57 48 45 52 45 20 6e 6f 64 65 6e 6f 20 3d  e WHERE nodeno =
0610: 20 24 69 4e 6f 64 65 0a 20 20 22 0a 20 20 73 65   $iNode.  ".  se
0620: 74 20 6e 6f 64 65 20 5b 64 62 20 6f 6e 65 20 24  t node [db one $
0630: 73 71 6c 5d 0a 0a 20 20 73 65 74 20 6e 43 65 6c  sql]..  set nCel
0640: 6c 20 5b 6c 6c 65 6e 67 74 68 20 24 6e 6f 64 65  l [llength $node
0650: 5d 0a 20 20 73 65 74 20 6e 43 6f 6f 72 64 20 5b  ].  set nCoord [
0660: 65 78 70 72 20 24 6e 44 69 6d 2a 32 5d 0a 20 20  expr $nDim*2].  
0670: 66 6f 72 20 7b 73 65 74 20 69 69 20 30 7d 20 7b  for {set ii 0} {
0680: 24 69 69 20 3c 20 24 6e 43 65 6c 6c 7d 20 7b 69  $ii < $nCell} {i
0690: 6e 63 72 20 69 69 7d 20 7b 0a 20 20 20 20 66 6f  ncr ii} {.    fo
06a0: 72 20 7b 73 65 74 20 6a 6a 20 31 7d 20 7b 24 6a  r {set jj 1} {$j
06b0: 6a 20 3c 3d 20 24 6e 43 6f 6f 72 64 7d 20 7b 69  j <= $nCoord} {i
06c0: 6e 63 72 20 6a 6a 7d 20 7b 0a 20 20 20 20 20 20  ncr jj} {.      
06d0: 73 65 74 20 6e 65 77 76 61 6c 20 5b 66 6f 72 6d  set newval [form
06e0: 61 74 20 22 25 2e 24 7b 69 50 72 65 63 7d 66 22  at "%.${iPrec}f"
06f0: 20 5b 6c 69 6e 64 65 78 20 24 6e 6f 64 65 20 24   [lindex $node $
0700: 69 69 20 24 6a 6a 5d 5d 0a 20 20 20 20 20 20 6c  ii $jj]].      l
0710: 73 65 74 20 6e 6f 64 65 20 24 69 69 20 24 6a 6a  set node $ii $jj
0720: 20 24 6e 65 77 76 61 6c 0a 20 20 20 20 7d 0a 20   $newval.    }. 
0730: 20 7d 0a 20 20 73 65 74 20 6e 6f 64 65 0a 7d 0a   }.  set node.}.
0740: 0a 70 72 6f 63 20 72 74 72 65 65 5f 6d 69 6e 63  .proc rtree_minc
0750: 65 6c 6c 73 20 7b 64 62 20 7a 54 61 62 7d 20 7b  ells {db zTab} {
0760: 0a 20 20 73 65 74 20 6e 20 5b 24 64 62 20 6f 6e  .  set n [$db on
0770: 65 20 22 73 65 6c 65 63 74 20 6c 65 6e 67 74 68  e "select length
0780: 28 64 61 74 61 29 20 46 52 4f 4d 20 24 7b 7a 54  (data) FROM ${zT
0790: 61 62 7d 5f 6e 6f 64 65 20 4c 49 4d 49 54 20 31  ab}_node LIMIT 1
07a0: 22 5d 0a 20 20 73 65 74 20 6e 4d 61 78 20 5b 65  "].  set nMax [e
07b0: 78 70 72 20 7b 69 6e 74 28 28 24 6e 2d 34 29 2f  xpr {int(($n-4)/
07c0: 28 38 2b 5b 72 74 72 65 65 5f 6e 64 69 6d 20 24  (8+[rtree_ndim $
07d0: 64 62 20 24 7a 54 61 62 5d 2a 32 2a 34 29 29 7d  db $zTab]*2*4))}
07e0: 5d 0a 20 20 72 65 74 75 72 6e 20 5b 65 78 70 72  ].  return [expr
07f0: 20 7b 69 6e 74 28 24 6e 4d 61 78 2f 33 29 7d 5d   {int($nMax/3)}]
0800: 0a 7d 0a 0a 23 20 41 6e 20 69 6e 74 65 67 72 69  .}..# An integri
0810: 74 79 20 63 68 65 63 6b 20 66 6f 72 20 74 68 65  ty check for the
0820: 20 72 74 72 65 65 20 24 7a 54 61 62 20 61 63 63   rtree $zTab acc
0830: 65 73 73 69 62 6c 65 20 76 69 61 20 64 61 74 61  essible via data
0840: 62 61 73 65 20 0a 23 20 63 6f 6e 6e 65 63 74 69  base .# connecti
0850: 6f 6e 20 24 64 62 2e 0a 23 0a 70 72 6f 63 20 72  on $db..#.proc r
0860: 74 72 65 65 5f 63 68 65 63 6b 20 7b 64 62 20 7a  tree_check {db z
0870: 54 61 62 7d 20 7b 0a 20 20 61 72 72 61 79 20 75  Tab} {.  array u
0880: 6e 73 65 74 20 3a 3a 63 68 65 63 6b 65 64 0a 20  nset ::checked. 
0890: 0a 20 20 23 20 43 68 65 63 6b 20 65 61 63 68 20  .  # Check each 
08a0: 72 2d 74 72 65 65 20 6e 6f 64 65 2e 0a 20 20 73  r-tree node..  s
08b0: 65 74 20 72 63 20 5b 63 61 74 63 68 20 7b 0a 20  et rc [catch {. 
08c0: 20 20 20 72 74 72 65 65 5f 6e 6f 64 65 5f 63 68     rtree_node_ch
08d0: 65 63 6b 20 24 64 62 20 24 7a 54 61 62 20 31 20  eck $db $zTab 1 
08e0: 5b 72 74 72 65 65 5f 64 65 70 74 68 20 24 64 62  [rtree_depth $db
08f0: 20 24 7a 54 61 62 5d 0a 20 20 7d 20 6d 73 67 5d   $zTab].  } msg]
0900: 0a 20 20 69 66 20 7b 24 72 63 20 26 26 20 24 6d  .  if {$rc && $m
0910: 73 67 20 6e 65 20 22 22 7d 20 7b 20 65 72 72 6f  sg ne ""} { erro
0920: 72 20 24 6d 73 67 20 7d 0a 0a 20 20 23 20 43 68  r $msg }..  # Ch
0930: 65 63 6b 20 74 68 61 74 20 74 68 65 20 5f 72 6f  eck that the _ro
0940: 77 69 64 20 61 6e 64 20 5f 70 61 72 65 6e 74 20  wid and _parent 
0950: 74 61 62 6c 65 73 20 68 61 76 65 20 74 68 65 20  tables have the 
0960: 72 69 67 68 74 20 0a 20 20 23 20 6e 75 6d 62 65  right .  # numbe
0970: 72 20 6f 66 20 65 6e 74 72 69 65 73 2e 0a 20 20  r of entries..  
0980: 73 65 74 20 6e 4e 6f 64 65 20 20 20 5b 24 64 62  set nNode   [$db
0990: 20 6f 6e 65 20 22 53 45 4c 45 43 54 20 63 6f 75   one "SELECT cou
09a0: 6e 74 28 2a 29 20 46 52 4f 4d 20 24 7b 7a 54 61  nt(*) FROM ${zTa
09b0: 62 7d 5f 6e 6f 64 65 22 5d 0a 20 20 73 65 74 20  b}_node"].  set 
09c0: 6e 52 6f 77 20 20 20 20 5b 24 64 62 20 6f 6e 65  nRow    [$db one
09d0: 20 22 53 45 4c 45 43 54 20 63 6f 75 6e 74 28 2a   "SELECT count(*
09e0: 29 20 46 52 4f 4d 20 24 7b 7a 54 61 62 7d 22 5d  ) FROM ${zTab}"]
09f0: 0a 20 20 73 65 74 20 6e 52 6f 77 69 64 20 20 5b  .  set nRowid  [
0a00: 24 64 62 20 6f 6e 65 20 22 53 45 4c 45 43 54 20  $db one "SELECT 
0a10: 63 6f 75 6e 74 28 2a 29 20 46 52 4f 4d 20 24 7b  count(*) FROM ${
0a20: 7a 54 61 62 7d 5f 72 6f 77 69 64 22 5d 0a 20 20  zTab}_rowid"].  
0a30: 73 65 74 20 6e 50 61 72 65 6e 74 20 5b 24 64 62  set nParent [$db
0a40: 20 6f 6e 65 20 22 53 45 4c 45 43 54 20 63 6f 75   one "SELECT cou
0a50: 6e 74 28 2a 29 20 46 52 4f 4d 20 24 7b 7a 54 61  nt(*) FROM ${zTa
0a60: 62 7d 5f 70 61 72 65 6e 74 22 5d 0a 0a 20 20 69  b}_parent"]..  i
0a70: 66 20 7b 24 6e 4e 6f 64 65 20 21 3d 20 28 24 6e  f {$nNode != ($n
0a80: 50 61 72 65 6e 74 2b 31 29 7d 20 7b 20 0a 20 20  Parent+1)} { .  
0a90: 20 20 65 72 72 6f 72 20 22 57 72 6f 6e 67 20 6e    error "Wrong n
0aa0: 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73  umber of entries
0ab0: 20 69 6e 20 24 7b 7a 54 61 62 7d 5f 70 61 72 65   in ${zTab}_pare
0ac0: 6e 74 22 0a 20 20 7d 0a 20 20 69 66 20 7b 24 6e  nt".  }.  if {$n
0ad0: 52 6f 77 20 21 3d 20 24 6e 52 6f 77 69 64 7d 20  Row != $nRowid} 
0ae0: 7b 20 0a 20 20 20 20 65 72 72 6f 72 20 22 57 72  { .    error "Wr
0af0: 6f 6e 67 20 6e 75 6d 62 65 72 20 6f 66 20 65 6e  ong number of en
0b00: 74 72 69 65 73 20 69 6e 20 24 7b 7a 54 61 62 7d  tries in ${zTab}
0b10: 5f 72 6f 77 69 64 22 0a 20 20 7d 0a 20 20 0a 20  _rowid".  }.  . 
0b20: 20 72 65 74 75 72 6e 20 24 72 63 0a 7d 0a 0a 70   return $rc.}..p
0b30: 72 6f 63 20 72 74 72 65 65 5f 6e 6f 64 65 5f 63  roc rtree_node_c
0b40: 68 65 63 6b 20 7b 64 62 20 7a 54 61 62 20 69 4e  heck {db zTab iN
0b50: 6f 64 65 20 69 44 65 70 74 68 7d 20 7b 0a 20 20  ode iDepth} {.  
0b60: 69 66 20 7b 5b 69 6e 66 6f 20 65 78 69 73 74 73  if {[info exists
0b70: 20 3a 3a 63 68 65 63 6b 65 64 28 24 69 4e 6f 64   ::checked($iNod
0b80: 65 29 5d 7d 20 7b 20 65 72 72 6f 72 20 22 53 65  e)]} { error "Se
0b90: 63 6f 6e 64 20 72 65 66 20 74 6f 20 24 69 4e 6f  cond ref to $iNo
0ba0: 64 65 22 20 7d 0a 20 20 73 65 74 20 3a 3a 63 68  de" }.  set ::ch
0bb0: 65 63 6b 65 64 28 24 69 4e 6f 64 65 29 20 31 0a  ecked($iNode) 1.
0bc0: 0a 20 20 73 65 74 20 6e 6f 64 65 20 5b 72 74 72  .  set node [rtr
0bd0: 65 65 5f 6e 6f 64 65 20 24 64 62 20 24 7a 54 61  ee_node $db $zTa
0be0: 62 20 24 69 4e 6f 64 65 5d 0a 20 20 69 66 20 7b  b $iNode].  if {
0bf0: 24 69 4e 6f 64 65 21 3d 31 20 26 26 20 5b 6c 6c  $iNode!=1 && [ll
0c00: 65 6e 67 74 68 20 24 6e 6f 64 65 5d 3d 3d 30 7d  ength $node]==0}
0c10: 20 7b 20 65 72 72 6f 72 20 22 4e 6f 20 73 75 63   { error "No suc
0c20: 68 20 6e 6f 64 65 3a 20 24 69 4e 6f 64 65 22 20  h node: $iNode" 
0c30: 7d 0a 0a 20 20 69 66 20 7b 24 69 4e 6f 64 65 20  }..  if {$iNode 
0c40: 21 3d 20 31 20 26 26 20 5b 6c 6c 65 6e 67 74 68  != 1 && [llength
0c50: 20 24 6e 6f 64 65 5d 3c 5b 72 74 72 65 65 5f 6d   $node]<[rtree_m
0c60: 69 6e 63 65 6c 6c 73 20 24 64 62 20 24 7a 54 61  incells $db $zTa
0c70: 62 5d 7d 20 7b 0a 20 20 20 20 70 75 74 73 20 22  b]} {.    puts "
0c80: 4e 6f 64 65 20 24 69 4e 6f 64 65 3a 20 48 61 73  Node $iNode: Has
0c90: 20 6f 6e 6c 79 20 5b 6c 6c 65 6e 67 74 68 20 24   only [llength $
0ca0: 6e 6f 64 65 5d 20 63 65 6c 6c 73 22 0a 20 20 20  node] cells".   
0cb0: 20 65 72 72 6f 72 20 22 22 0a 20 20 7d 0a 20 20   error "".  }.  
0cc0: 69 66 20 7b 24 69 4e 6f 64 65 20 3d 3d 20 31 20  if {$iNode == 1 
0cd0: 26 26 20 5b 6c 6c 65 6e 67 74 68 20 24 6e 6f 64  && [llength $nod
0ce0: 65 5d 3d 3d 31 20 26 26 20 5b 72 74 72 65 65 5f  e]==1 && [rtree_
0cf0: 64 65 70 74 68 20 24 64 62 20 24 7a 54 61 62 5d  depth $db $zTab]
0d00: 3e 30 7d 20 7b 0a 20 20 20 20 73 65 74 20 64 65  >0} {.    set de
0d10: 70 74 68 20 5b 72 74 72 65 65 5f 64 65 70 74 68  pth [rtree_depth
0d20: 20 24 64 62 20 24 7a 54 61 62 5d 0a 20 20 20 20   $db $zTab].    
0d30: 70 75 74 73 20 22 4e 6f 64 65 20 24 69 4e 6f 64  puts "Node $iNod
0d40: 65 3a 20 48 61 73 20 6f 6e 6c 79 20 31 20 63 68  e: Has only 1 ch
0d50: 69 6c 64 20 28 74 72 65 65 20 64 65 70 74 68 20  ild (tree depth 
0d60: 69 73 20 24 64 65 70 74 68 29 22 0a 20 20 20 20  is $depth)".    
0d70: 65 72 72 6f 72 20 22 22 0a 20 20 7d 0a 0a 20 20  error "".  }..  
0d80: 73 65 74 20 6e 44 69 6d 20 5b 65 78 70 72 20 7b  set nDim [expr {
0d90: 28 5b 6c 6c 65 6e 67 74 68 20 5b 6c 69 6e 64 65  ([llength [linde
0da0: 78 20 24 6e 6f 64 65 20 30 5d 5d 2d 31 29 2f 32  x $node 0]]-1)/2
0db0: 7d 5d 0a 0a 20 20 69 66 20 7b 24 69 44 65 70 74  }]..  if {$iDept
0dc0: 68 20 3e 20 30 7d 20 7b 0a 20 20 20 20 73 65 74  h > 0} {.    set
0dd0: 20 64 20 5b 65 78 70 72 20 24 69 44 65 70 74 68   d [expr $iDepth
0de0: 2d 31 5d 0a 20 20 20 20 66 6f 72 65 61 63 68 20  -1].    foreach 
0df0: 63 65 6c 6c 20 24 6e 6f 64 65 20 7b 0a 20 20 20  cell $node {.   
0e00: 20 20 20 73 65 74 20 73 68 6f 75 6c 64 62 65 20     set shouldbe 
0e10: 5b 72 74 72 65 65 5f 6e 6f 64 65 5f 63 68 65 63  [rtree_node_chec
0e20: 6b 20 24 64 62 20 24 7a 54 61 62 20 5b 6c 69 6e  k $db $zTab [lin
0e30: 64 65 78 20 24 63 65 6c 6c 20 30 5d 20 24 64 5d  dex $cell 0] $d]
0e40: 0a 20 20 20 20 20 20 69 66 20 7b 24 63 65 6c 6c  .      if {$cell
0e50: 20 6e 65 20 24 73 68 6f 75 6c 64 62 65 7d 20 7b   ne $shouldbe} {
0e60: 0a 20 20 20 20 20 20 20 20 70 75 74 73 20 22 4e  .        puts "N
0e70: 6f 64 65 20 24 69 4e 6f 64 65 3a 20 43 65 6c 6c  ode $iNode: Cell
0e80: 20 69 73 3a 20 7b 24 63 65 6c 6c 7d 2c 20 73 68   is: {$cell}, sh
0e90: 6f 75 6c 64 20 62 65 20 7b 24 73 68 6f 75 6c 64  ould be {$should
0ea0: 62 65 7d 22 0a 20 20 20 20 20 20 20 20 65 72 72  be}".        err
0eb0: 6f 72 20 22 22 0a 20 20 20 20 20 20 7d 0a 20 20  or "".      }.  
0ec0: 20 20 7d 0a 20 20 7d 0a 0a 20 20 73 65 74 20 6d    }.  }..  set m
0ed0: 61 70 70 69 6e 67 5f 74 61 62 6c 65 20 22 24 7b  apping_table "${
0ee0: 7a 54 61 62 7d 5f 70 61 72 65 6e 74 22 20 0a 20  zTab}_parent" . 
0ef0: 20 73 65 74 20 6d 61 70 70 69 6e 67 5f 73 71 6c   set mapping_sql
0f00: 20 22 53 45 4c 45 43 54 20 70 61 72 65 6e 74 6e   "SELECT parentn
0f10: 6f 64 65 20 46 52 4f 4d 20 24 6d 61 70 70 69 6e  ode FROM $mappin
0f20: 67 5f 74 61 62 6c 65 20 57 48 45 52 45 20 72 6f  g_table WHERE ro
0f30: 77 69 64 20 3d 20 5c 24 72 6f 77 69 64 22 0a 20  wid = \$rowid". 
0f40: 20 69 66 20 7b 24 69 44 65 70 74 68 3d 3d 30 7d   if {$iDepth==0}
0f50: 20 7b 20 0a 20 20 20 20 73 65 74 20 6d 61 70 70   { .    set mapp
0f60: 69 6e 67 5f 74 61 62 6c 65 20 22 24 7b 7a 54 61  ing_table "${zTa
0f70: 62 7d 5f 72 6f 77 69 64 22 0a 20 20 20 20 73 65  b}_rowid".    se
0f80: 74 20 6d 61 70 70 69 6e 67 5f 73 71 6c 20 22 53  t mapping_sql "S
0f90: 45 4c 45 43 54 20 6e 6f 64 65 6e 6f 20 46 52 4f  ELECT nodeno FRO
0fa0: 4d 20 24 6d 61 70 70 69 6e 67 5f 74 61 62 6c 65  M $mapping_table
0fb0: 20 57 48 45 52 45 20 72 6f 77 69 64 20 3d 20 5c   WHERE rowid = \
0fc0: 24 72 6f 77 69 64 22 0a 20 20 7d 0a 20 20 66 6f  $rowid".  }.  fo
0fd0: 72 65 61 63 68 20 63 65 6c 6c 20 24 6e 6f 64 65  reach cell $node
0fe0: 20 7b 0a 20 20 20 20 73 65 74 20 72 6f 77 69 64   {.    set rowid
0ff0: 20 5b 6c 69 6e 64 65 78 20 24 63 65 6c 6c 20 30   [lindex $cell 0
1000: 5d 0a 20 20 20 20 73 65 74 20 6d 61 70 70 69 6e  ].    set mappin
1010: 67 20 5b 64 62 20 6f 6e 65 20 24 6d 61 70 70 69  g [db one $mappi
1020: 6e 67 5f 73 71 6c 5d 0a 20 20 20 20 69 66 20 7b  ng_sql].    if {
1030: 24 6d 61 70 70 69 6e 67 20 21 3d 20 24 69 4e 6f  $mapping != $iNo
1040: 64 65 7d 20 7b 0a 20 20 20 20 20 20 70 75 74 73  de} {.      puts
1050: 20 22 4e 6f 64 65 20 24 69 4e 6f 64 65 3a 20 24   "Node $iNode: $
1060: 6d 61 70 70 69 6e 67 5f 74 61 62 6c 65 20 65 6e  mapping_table en
1070: 74 72 79 20 66 6f 72 20 63 65 6c 6c 20 24 72 6f  try for cell $ro
1080: 77 69 64 20 69 73 20 24 6d 61 70 70 69 6e 67 22  wid is $mapping"
1090: 0a 20 20 20 20 20 20 65 72 72 6f 72 20 22 22 0a  .      error "".
10a0: 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 73 65 74      }.  }..  set
10b0: 20 72 65 74 20 5b 6c 69 73 74 20 24 69 4e 6f 64   ret [list $iNod
10c0: 65 5d 0a 20 20 66 6f 72 20 7b 73 65 74 20 69 69  e].  for {set ii
10d0: 20 31 7d 20 7b 24 69 69 20 3c 3d 20 24 6e 44 69   1} {$ii <= $nDi
10e0: 6d 2a 32 7d 20 7b 69 6e 63 72 20 69 69 7d 20 7b  m*2} {incr ii} {
10f0: 0a 20 20 20 20 73 65 74 20 66 20 5b 6c 69 6e 64  .    set f [lind
1100: 65 78 20 24 6e 6f 64 65 20 30 20 24 69 69 5d 0a  ex $node 0 $ii].
1110: 20 20 20 20 66 6f 72 65 61 63 68 20 63 65 6c 6c      foreach cell
1120: 20 24 6e 6f 64 65 20 7b 0a 20 20 20 20 20 20 73   $node {.      s
1130: 65 74 20 66 32 20 5b 6c 69 6e 64 65 78 20 24 63  et f2 [lindex $c
1140: 65 6c 6c 20 24 69 69 5d 0a 20 20 20 20 20 20 69  ell $ii].      i
1150: 66 20 7b 28 24 69 69 25 32 29 3d 3d 31 20 26 26  f {($ii%2)==1 &&
1160: 20 24 66 32 3c 24 66 7d 20 7b 73 65 74 20 66 20   $f2<$f} {set f 
1170: 24 66 32 7d 0a 20 20 20 20 20 20 69 66 20 7b 28  $f2}.      if {(
1180: 24 69 69 25 32 29 3d 3d 30 20 26 26 20 24 66 32  $ii%2)==0 && $f2
1190: 3e 24 66 7d 20 7b 73 65 74 20 66 20 24 66 32 7d  >$f} {set f $f2}
11a0: 0a 20 20 20 20 7d 0a 20 20 20 20 6c 61 70 70 65  .    }.    lappe
11b0: 6e 64 20 72 65 74 20 24 66 0a 20 20 7d 0a 20 20  nd ret $f.  }.  
11c0: 72 65 74 75 72 6e 20 24 72 65 74 0a 7d 0a 0a 70  return $ret.}..p
11d0: 72 6f 63 20 72 74 72 65 65 5f 64 75 6d 70 20 7b  roc rtree_dump {
11e0: 64 62 20 7a 54 61 62 7d 20 7b 0a 20 20 73 65 74  db zTab} {.  set
11f0: 20 7a 52 65 74 20 22 22 0a 20 20 73 65 74 20 6e   zRet "".  set n
1200: 44 69 6d 20 5b 65 78 70 72 20 7b 28 28 5b 6c 6c  Dim [expr {(([ll
1210: 65 6e 67 74 68 20 5b 24 64 62 20 65 76 61 6c 20  ength [$db eval 
1220: 22 70 72 61 67 6d 61 20 74 61 62 6c 65 5f 69 6e  "pragma table_in
1230: 66 6f 28 24 7a 54 61 62 29 22 5d 5d 2f 36 29 2d  fo($zTab)"]]/6)-
1240: 31 29 2f 32 7d 5d 0a 20 20 73 65 74 20 73 71 6c  1)/2}].  set sql
1250: 20 22 53 45 4c 45 43 54 20 6e 6f 64 65 6e 6f 2c   "SELECT nodeno,
1260: 20 72 74 72 65 65 6e 6f 64 65 28 24 6e 44 69 6d   rtreenode($nDim
1270: 2c 20 64 61 74 61 29 20 41 53 20 6e 6f 64 65 20  , data) AS node 
1280: 46 52 4f 4d 20 24 7b 7a 54 61 62 7d 5f 6e 6f 64  FROM ${zTab}_nod
1290: 65 22 0a 20 20 24 64 62 20 65 76 61 6c 20 24 73  e".  $db eval $s
12a0: 71 6c 20 7b 0a 20 20 20 20 61 70 70 65 6e 64 20  ql {.    append 
12b0: 7a 52 65 74 20 5b 66 6f 72 6d 61 74 20 22 25 20  zRet [format "% 
12c0: 2d 31 30 73 20 25 73 5c 6e 22 20 24 6e 6f 64 65  -10s %s\n" $node
12d0: 6e 6f 20 24 6e 6f 64 65 5d 0a 20 20 7d 0a 20 20  no $node].  }.  
12e0: 73 65 74 20 7a 52 65 74 0a 7d 0a 0a 70 72 6f 63  set zRet.}..proc
12f0: 20 72 74 72 65 65 5f 6e 6f 64 65 74 72 65 65 64   rtree_nodetreed
1300: 75 6d 70 20 7b 64 62 20 7a 54 61 62 20 7a 49 6e  ump {db zTab zIn
1310: 64 65 6e 74 20 69 44 65 70 74 68 20 69 4e 6f 64  dent iDepth iNod
1320: 65 7d 20 7b 0a 20 20 73 65 74 20 72 65 74 20 22  e} {.  set ret "
1330: 22 0a 20 20 73 65 74 20 6e 6f 64 65 20 5b 72 74  ".  set node [rt
1340: 72 65 65 5f 6e 6f 64 65 20 24 64 62 20 24 7a 54  ree_node $db $zT
1350: 61 62 20 24 69 4e 6f 64 65 20 31 5d 0a 20 20 61  ab $iNode 1].  a
1360: 70 70 65 6e 64 20 72 65 74 20 5b 66 6f 72 6d 61  ppend ret [forma
1370: 74 20 22 25 2d 33 64 20 25 73 25 73 5c 6e 22 20  t "%-3d %s%s\n" 
1380: 24 69 4e 6f 64 65 20 24 7a 49 6e 64 65 6e 74 20  $iNode $zIndent 
1390: 24 6e 6f 64 65 5d 0a 20 20 69 66 20 7b 24 69 44  $node].  if {$iD
13a0: 65 70 74 68 3e 30 7d 20 7b 0a 20 20 20 20 66 6f  epth>0} {.    fo
13b0: 72 65 61 63 68 20 63 65 6c 6c 20 24 6e 6f 64 65  reach cell $node
13c0: 20 7b 0a 20 20 20 20 20 20 73 65 74 20 69 20 5b   {.      set i [
13d0: 6c 69 6e 64 65 78 20 24 63 65 6c 6c 20 30 5d 0a  lindex $cell 0].
13e0: 20 20 20 20 20 20 61 70 70 65 6e 64 20 72 65 74        append ret
13f0: 20 5b 72 74 72 65 65 5f 6e 6f 64 65 74 72 65 65   [rtree_nodetree
1400: 64 75 6d 70 20 24 64 62 20 24 7a 54 61 62 20 22  dump $db $zTab "
1410: 24 7a 49 6e 64 65 6e 74 20 20 22 20 5b 65 78 70  $zIndent  " [exp
1420: 72 20 24 69 44 65 70 74 68 2d 31 5d 20 24 69 5d  r $iDepth-1] $i]
1430: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 73 65 74  .    }.  }.  set
1440: 20 72 65 74 0a 7d 0a 0a 70 72 6f 63 20 72 74 72   ret.}..proc rtr
1450: 65 65 5f 74 72 65 65 64 75 6d 70 20 7b 64 62 20  ee_treedump {db 
1460: 7a 54 61 62 7d 20 7b 0a 20 20 73 65 74 20 64 20  zTab} {.  set d 
1470: 5b 72 74 72 65 65 5f 64 65 70 74 68 20 24 64 62  [rtree_depth $db
1480: 20 24 7a 54 61 62 5d 0a 20 20 72 74 72 65 65 5f   $zTab].  rtree_
1490: 6e 6f 64 65 74 72 65 65 64 75 6d 70 20 24 64 62  nodetreedump $db
14a0: 20 24 7a 54 61 62 20 22 22 20 24 64 20 31 0a 7d   $zTab "" $d 1.}
14b0: 0a 0a                                            ..