**    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 
................................................................................
#else
  #include "sqlite3.h"
#endif

#include <string.h>
#include <assert.h>

#ifndef SQLITE_CORE
  typedef sqlite3_int64 i64;
  typedef unsigned char u8;
  typedef unsigned int u32;
#endif

typedef struct Rtree Rtree;
typedef struct RtreeCursor RtreeCursor;
typedef struct RtreeNode RtreeNode;
typedef struct RtreeCell RtreeCell;
typedef struct RtreeConstraint RtreeConstraint;

**    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.5 2008/06/23 15:55:52 danielk1977 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 
................................................................................
#else
  #include "sqlite3.h"
#endif

#include <string.h>
#include <assert.h>


typedef sqlite3_int64 i64;
typedef unsigned char u8;
typedef unsigned int u32;


typedef struct Rtree Rtree;
typedef struct RtreeCursor RtreeCursor;
typedef struct RtreeNode RtreeNode;
typedef struct RtreeCell RtreeCell;
typedef struct RtreeConstraint RtreeConstraint;

#
#    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.
#
#***********************************************************************
# This file runs all rtree related tests.
#
# $Id: rtree.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $

set testdir [file join [file dirname $argv0] .. .. test]
source $testdir/tester.tcl
rename finish_test really_finish_test
proc finish_test {} {}
set ISQUICK 1

set EXCLUDE {
  rtree.test
}

# Files to include in the test.  If this list is empty then everything
# that is not in the EXCLUDE list is run.
#
set INCLUDE {
}

foreach testfile [lsort -dictionary [glob [file dirname $argv0]/*.test]] {
  set tail [file tail $testfile]
  if {[lsearch -exact $EXCLUDE $tail]>=0} continue
  if {[llength $INCLUDE]>0 && [lsearch -exact $INCLUDE $tail]<0} continue
  source $testfile
  catch {db close}
  if {$sqlite_open_file_count>0} {
    puts "$tail did not close all files: $sqlite_open_file_count"
    incr nErr
    lappend ::failList $tail
    set sqlite_open_file_count 0
  }
}

set sqlite_open_file_count 0
really_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: rtree1.test,v 1.2 2008/05/26 20:49:04 drh Exp $
#


set testdir [file join [file dirname $argv0] .. .. test]

source $testdir/tester.tcl

# Test plan:
#
#   rtree-1.*: Creating/destroying r-tree tables.
#   rtree-2.*: Test the implicit constraints - unique rowid and
#              (coord[N]<=coord[N+1]) for even values of N. Also

#    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: rtree1.test,v 1.3 2008/06/23 15:55:52 danielk1977 Exp $
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
}
source $testdir/tester.tcl

# Test plan:
#
#   rtree-1.*: Creating/destroying r-tree tables.
#   rtree-2.*: Test the implicit constraints - unique rowid and
#              (coord[N]<=coord[N+1]) for even values of N. Also

#    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 {
  finish_test
  return
}

set ::NROW   1000
set ::NDEL     10
set ::NSELECT 100






for {set nDim 1} {$nDim <= 5} {incr nDim} {

  do_test rtree2-$nDim.1 {
    set cols [list]
    foreach c [list c0 c1 c2 c3 c4 c5 c6 c7 c8 c9] {
      lappend cols "$c REAL"

#    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.3 2008/06/23 15:55:52 danielk1977 Exp $
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl


ifcapable !rtree {
  finish_test
  return
}

set ::NROW   1000
set ::NDEL     10
set ::NSELECT 100

if {[info exists ISQUICK] && $ISQUICK} {
  set ::NROW 100
  set ::NSELECT 10
}

for {set nDim 1} {$nDim <= 5} {incr nDim} {

  do_test rtree2-$nDim.1 {
    set cols [list]
    foreach c [list c0 c1 c2 c3 c4 c5 c6 c7 c8 c9] {
      lappend cols "$c REAL"

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# The focus of this file is testing that the r-tree correctly handles
# out-of-memory conditions.
#
# $Id: rtree3.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
#


set testdir [file join [file dirname $argv0] .. .. test]

source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# The focus of this file is testing that the r-tree correctly handles
# out-of-memory conditions.
#
# $Id: rtree3.test,v 1.2 2008/06/23 15:55:52 danielk1977 Exp $
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
} 
source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

#    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.2 2008/05/28 13:49:35 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}]
}

................................................................................
  } {}

  # 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]}]

#    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.3 2008/06/23 15:55:52 danielk1977 Exp $
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
} 
source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

set ::NROW 2500
if {[info exists ISQUICK] && $ISQUICK} {
  set ::NROW 250
}

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

................................................................................
  } {}

  # 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<$::NROW} {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]}]

#
# Once the macros above are defined, the rest of this make script will
# build the SQLite library and testing tools.
################################################################################

# This is how we compile
#
TCCX = $(TCC) $(OPTS) -I. -I$(TOP)/src -I$(TOP)

# Object files for the SQLite library.
#
LIBOBJ+= alter.o analyze.o attach.o auth.o bitvec.o btmutex.o btree.o build.o \
         callback.o complete.o date.o delete.o \
         expr.o fault.o func.o global.o hash.o insert.o journal.o loadext.o \
         main.o malloc.o mem1.o mem2.o mem3.o mem4.o mem5.o \

#
# Once the macros above are defined, the rest of this make script will
# build the SQLite library and testing tools.
################################################################################

# This is how we compile
#
TCCX = $(TCC) $(OPTS) -I. -I$(TOP)/src -I$(TOP) -I$(TOP)/ext/rtree

# Object files for the SQLite library.
#
LIBOBJ+= alter.o analyze.o attach.o auth.o bitvec.o btmutex.o btree.o build.o \
         callback.o complete.o date.o delete.o \
         expr.o fault.o func.o global.o hash.o insert.o journal.o loadext.o \
         main.o malloc.o mem1.o mem2.o mem3.o mem4.o mem5.o \

#
#    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.
#
#***********************************************************************
#
# $Id: permutations.test,v 1.2 2008/06/21 19:10:27 danielk1977 Exp $

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

# Argument processing.
#
set ::testmode [lindex $argv 0]
................................................................................
# Run some ioerr-tests in autovacuum mode.
#
run_tests "autovacuum_ioerr" -description {
  Run ioerr.test in autovacuum mode.
} -presql {
  pragma auto_vacuum = 1
} -include ioerr.test
























# End of tests
#############################################################################

if {$::testmode eq "targets"} { puts "" ; exit }

# Restore the [sqlite3] command.

#
#    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.
#
#***********************************************************************
#
# $Id: permutations.test,v 1.3 2008/06/23 15:55:52 danielk1977 Exp $

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

# Argument processing.
#
set ::testmode [lindex $argv 0]
................................................................................
# Run some ioerr-tests in autovacuum mode.
#
run_tests "autovacuum_ioerr" -description {
  Run ioerr.test in autovacuum mode.
} -presql {
  pragma auto_vacuum = 1
} -include ioerr.test

# run_tests "crash_safe_append" -description {
#   Run crash.test with persistent journals on a SAFE_APPEND file-system.
# } -initialize {
#   rename crashsql sa_crashsql
#   proc crashsql {args} {
#     set options [lrange $args 0 [expr {[llength $args]-2}]]
#     lappend options -char safe_append
#     set sql [lindex $args end]
#     lappend options "
#       PRAGMA journal_mode=persistent;
#       $sql
#     "
#     set fd [open test.db-journal w]
#     puts $fd [string repeat 1234567890 100000]
#     close $fd
#     eval sa_crashsql $options
#   }
# } -shutdown {
#   rename crashsql {}
#   rename sa_crashsql crashsql
# } -include crash.test


# End of tests
#############################################################################

if {$::testmode eq "targets"} { puts "" ; exit }

# Restore the [sqlite3] command.

#
#    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.
#
#***********************************************************************
# This file runs all rtree related tests.
#
# $Id: rtree.test,v 1.1 2008/06/23 15:55:52 danielk1977 Exp $

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

rename finish_test rtree_finish_test
proc finish_test {} {}

set RTREE_EXCLUDE { }
if {[info exists ISQUICK] && $ISQUICK} { 
  set RTREE_EXCLUDE rtree3.test
}

set rtreedir [file join $testdir .. ext rtree]

foreach testfile [lsort -dictionary [glob $rtreedir/*.test]] {
  set tail [file tail $testfile]
  if {[lsearch -exact $RTREE_EXCLUDE $tail]>=0} continue
  source $testfile
  catch {db close}
  if {$sqlite_open_file_count>0} {
    puts "$tail did not close all files: $sqlite_open_file_count"
    incr nErr
    lappend ::failList $tail
    set sqlite_open_file_count 0
  }
}

set sqlite_open_file_count 0
rtree_finish_test
rename finish_test {}
rename rtree_finish_test finish_test