**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
**
** $Id: rtree.c,v 1.3 2008/05/26 20:49:03 drh Exp $
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
................................................................................
**
** The second of each pair of bytes identifies the coordinate column
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int rc = SQLITE_OK;
  int ii;

  int iIdx = 0;
  char zIdxStr[RTREE_MAX_DIMENSIONS*2+1];
  memset(zIdxStr, 0, RTREE_MAX_DIMENSIONS*2+1);

  assert( pIdxInfo->idxStr==0 );
  for(ii=0; ii<pIdxInfo->nConstraint; ii++){
    struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];

    if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
      /* We have an equality constraint on the rowid. Use strategy 1. */
................................................................................
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
      }
      if( op ){



























        zIdxStr[iIdx++] = op;
        zIdxStr[iIdx++] = (char)(p->iColumn-1) + 'a';
        pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
        pIdxInfo->aConstraintUsage[ii].omit = 1;
      }
    }
  }

  pIdxInfo->idxNum = 2;

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
**
** $Id: rtree.c,v 1.4 2008/05/27 00:06:02 drh Exp $
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
................................................................................
**
** The second of each pair of bytes identifies the coordinate column
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int rc = SQLITE_OK;
  int ii, cCol;

  int iIdx = 0;
  char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
  memset(zIdxStr, 0, sizeof(zIdxStr));

  assert( pIdxInfo->idxStr==0 );
  for(ii=0; ii<pIdxInfo->nConstraint; ii++){
    struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];

    if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
      /* We have an equality constraint on the rowid. Use strategy 1. */
................................................................................
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
      }
      if( op ){
        /* Make sure this particular constraint has not been used before.
        ** If it has been used before, ignore it.
        **
        ** A <= or < can be used if there is a prior >= or >.
        ** A >= or > can be used if there is a prior < or <=.
        ** A <= or < is disqualified if there is a prior <=, <, or ==.
        ** A >= or > is disqualified if there is a prior >=, >, or ==.
        ** A == is disqualifed if there is any prior constraint.
        */
        int j, opmsk;
        static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
        assert( compatible[RTREE_EQ & 7]==0 );
        assert( compatible[RTREE_LT & 7]==1 );
        assert( compatible[RTREE_LE & 7]==1 );
        assert( compatible[RTREE_GT & 7]==2 );
        assert( compatible[RTREE_GE & 7]==2 );
        cCol = p->iColumn - 1 + 'a';
        opmsk = compatible[op & 7];
        for(j=0; j<iIdx; j+=2){
          if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
            op = 0;
            break;
          }
        }
      }
      if( op ){
        assert( iIdx<sizeof(zIdxStr)-1 );
        zIdxStr[iIdx++] = op;
        zIdxStr[iIdx++] = cCol;
        pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
        pIdxInfo->aConstraintUsage[ii].omit = 1;
      }
    }
  }

  pIdxInfo->idxNum = 2;

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# The focus of this file is testing the r-tree extension.
#
# $Id: rtree2.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
#

set testdir [file join [file dirname $argv0] .. .. test]
source $testdir/tester.tcl
source [file join [file dirname $argv0] rtree_util.tcl]

ifcapable !rtree {
................................................................................
      CREATE TABLE t2 (ii, $cols);
    "
  } {}

  do_test rtree2-$nDim.2 {
    db transaction {
      for {set ii 0} {$ii < $::NROW} {incr ii} {
#puts "Row $ii"
        set values [list]
        for {set jj 0} {$jj<$nDim*2} {incr jj} {
          lappend values [expr int(rand()*1000)]
        }
        set values [join $values ,]
#puts [rtree_treedump db t1]
#puts "INSERT INTO t2 VALUES($ii, $values)"
        set rc [catch {db eval "INSERT INTO t1 VALUES($ii, $values)"}]
        if {$rc} {
          incr ii -1
        } else {
          db eval "INSERT INTO t2 VALUES($ii, $values)"
        }
#if {[rtree_check db t1]} {
#puts [rtree_treedump db t1]
#exit
#}
      }
    }

    set t1 [execsql {SELECT * FROM t1 ORDER BY ii}]
    set t2 [execsql {SELECT * FROM t2 ORDER BY ii}]
    set rc [expr {$t1 eq $t2}]
    if {$rc != 1} {
................................................................................
      }
      set where [join $where " AND "]

      set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
      set t2 [execsql "SELECT * FROM t2 WHERE $where ORDER BY ii"]
      set rc [expr {$t1 eq $t2}]
      if {$rc != 1} {
puts $where
        puts $t1
        puts $t2
puts [rtree_treedump db t1]
breakpoint
set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
exit
      }
      set rc
    } {1}
  }

  for {set ii 0} {$ii < $::NROW} {incr ii $::NDEL} {
    #puts [rtree_treedump db t1]
................................................................................
      DROP TABLE t1;
      DROP TABLE t2;
    }
  } {}
}

finish_test

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# The focus of this file is testing the r-tree extension.
#
# $Id: rtree2.test,v 1.2 2008/05/27 00:06:02 drh Exp $
#

set testdir [file join [file dirname $argv0] .. .. test]
source $testdir/tester.tcl
source [file join [file dirname $argv0] rtree_util.tcl]

ifcapable !rtree {
................................................................................
      CREATE TABLE t2 (ii, $cols);
    "
  } {}

  do_test rtree2-$nDim.2 {
    db transaction {
      for {set ii 0} {$ii < $::NROW} {incr ii} {
        #puts "Row $ii"
        set values [list]
        for {set jj 0} {$jj<$nDim*2} {incr jj} {
          lappend values [expr int(rand()*1000)]
        }
        set values [join $values ,]
        #puts [rtree_treedump db t1]
        #puts "INSERT INTO t2 VALUES($ii, $values)"
        set rc [catch {db eval "INSERT INTO t1 VALUES($ii, $values)"}]
        if {$rc} {
          incr ii -1
        } else {
          db eval "INSERT INTO t2 VALUES($ii, $values)"
        }
        #if {[rtree_check db t1]} {
          #puts [rtree_treedump db t1]
          #exit
        #}
      }
    }

    set t1 [execsql {SELECT * FROM t1 ORDER BY ii}]
    set t2 [execsql {SELECT * FROM t2 ORDER BY ii}]
    set rc [expr {$t1 eq $t2}]
    if {$rc != 1} {
................................................................................
      }
      set where [join $where " AND "]

      set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
      set t2 [execsql "SELECT * FROM t2 WHERE $where ORDER BY ii"]
      set rc [expr {$t1 eq $t2}]
      if {$rc != 1} {
        #puts $where
        puts $t1
        puts $t2
        #puts [rtree_treedump db t1]
        #breakpoint
        #set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
        #exit
      }
      set rc
    } {1}
  }

  for {set ii 0} {$ii < $::NROW} {incr ii $::NDEL} {
    #puts [rtree_treedump db t1]
................................................................................
      DROP TABLE t1;
      DROP TABLE t2;
    }
  } {}
}

finish_test

# 2008 May 23
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# Randomized test cases for the rtree extension.
#
# $Id: rtree4.test,v 1.1 2008/05/27 00:06:02 drh Exp $
#

set testdir [file join [file dirname $argv0] .. .. test]
source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

# Return a floating point number between -X and X.
# 
proc rand {X} {
  return [expr {int((rand()-0.5)*1024.0*$X)/512.0}]
}

# Return a positive floating point number less than or equal to X
#
proc randincr {X} {
  while 1 {
    set r [expr {int(rand()*$X*32.0)/32.0}]
    if {$r>0.0} {return $r}
  }
}

# Scramble the $inlist into a random order.
#
proc scramble {inlist} {
  set y {}
  foreach x $inlist {
    lappend y [list [expr {rand()}] $x]
  }
  set y [lsort $y]
  set outlist {}
  foreach x $y {
    lappend outlist [lindex $x 1]
  }
  return $outlist
}

# Always use the same random seed so that the sequence of tests
# is repeatable.
#
expr {srand(1234)}

# Run these tests for all number of dimensions between 1 and 5.
#
for {set nDim 1} {$nDim<=5} {incr nDim} {

  # Construct an rtree virtual table and an ordinary btree table
  # to mirror it.  The ordinary table should be much slower (since
  # it has to do a full table scan) but should give the exact same
  # answers.
  #
  do_test rtree4-$nDim.1 {
    set clist {}
    set cklist {}
    for {set i 0} {$i<$nDim} {incr i} {
      lappend clist mn$i mx$i
      lappend cklist "mn$i<mx$i"
    }
    db eval "DROP TABLE IF EXISTS rx"
    db eval "DROP TABLE IF EXISTS bx"
    db eval "CREATE VIRTUAL TABLE rx USING rtree(id, [join $clist ,])"
    db eval "CREATE TABLE bx(id INTEGER PRIMARY KEY,\
                [join $clist ,], CHECK( [join $cklist { AND }] ))"
  } {}

  # Do many insertions of small objects.  Do both overlapping and
  # contained-within queries after each insert to verify that all
  # is well.
  #
  unset -nocomplain where
  for {set i 1} {$i<2500} {incr i} {
    # Do a random insert
    #
    do_test rtree-$nDim.2.$i.1 {
      set vlist {}
      for {set j 0} {$j<$nDim} {incr j} {
        set mn [rand 10000]
        set mx [expr {$mn+[randincr 50]}]
        lappend vlist $mn $mx
      }
      db eval "INSERT INTO rx VALUES(NULL, [join $vlist ,])"
      db eval "INSERT INTO bx VALUES(NULL, [join $vlist ,])"
    } {}

    # Do a contained-in query on all dimensions
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mn$j>=$mn mx$j<=$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.2 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query on all dimensions
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mx$j>=$mn mn$j<=$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.3 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do a contained-in query with surplus contraints at the beginning.
    # This should force a full-table scan on the rtree.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      lappend where mn$j>-10000 mx$j<10000
    }
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mn$j>=$mn mx$j<=$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.3 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query with surplus contraints at the beginning.
    # This should force a full-table scan on the rtree.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      lappend where mn$j>=-10000 mx$j<=10000
    }
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mx$j>$mn mn$j<$mx
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.4 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do a contained-in query with surplus contraints at the end
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mn$j>=$mn mx$j<$mx
    }
    for {set j [expr {$nDim-1}]} {$j>=0} {incr j -1} {
      lappend where mn$j>=-10000 mx$j<10000
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.5 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query with surplus contraints at the end
    #
    set where {}
    for {set j [expr {$nDim-1}]} {$j>=0} {incr j -1} {
      set mn [rand 10000]
      set mx [expr {$mn+[randincr 500]}]
      lappend where mx$j>$mn mn$j<=$mx
    }
    for {set j 0} {$j<$nDim} {incr j} {
      lappend where mx$j>-10000 mn$j<=10000
    }
    set where "WHERE [join $where { AND }]"
    do_test rtree-$nDim.2.$i.6 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do a contained-in query with surplus contraints where the 
    # constraints appear in a random order.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn1 [rand 10000]
      set mn2 [expr {$mn1+[randincr 100]}]
      set mx1 [expr {$mn2+[randincr 400]}]
      set mx2 [expr {$mx1+[randincr 100]}]
      lappend where mn$j>=$mn1 mn$j>$mn2 mx$j<$mx1 mx$j<=$mx2
    }
    set where "WHERE [join [scramble $where] { AND }]"
    do_test rtree-$nDim.2.$i.7 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

    # Do an overlaps query with surplus contraints where the
    # constraints appear in a random order.
    #
    set where {}
    for {set j 0} {$j<$nDim} {incr j} {
      set mn1 [rand 10000]
      set mn2 [expr {$mn1+[randincr 100]}]
      set mx1 [expr {$mn2+[randincr 400]}]
      set mx2 [expr {$mx1+[randincr 100]}]
      lappend where mx$j>=$mn1 mx$j>$mn2 mn$j<$mx1 mn$j<=$mx2
    }
    set where "WHERE [join [scramble $where] { AND }]"
    do_test rtree-$nDim.2.$i.8 {
      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]

  }

}

finish_test