18 files changed, 3000 insertions, 0 deletions

diff --git a/test/rtree/Makefile.am b/test/rtree/Makefile.am
new file mode 100644
index 0000000..a664104
--- /dev/null
+++ b/test/rtree/Makefile.am
@@ -0,0 +1,41 @@
+AM_CPPFLAGS = \
+	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/test/include \
+	$(CXXFLAGS_UNITTESTS)
+
+DISTCLEANFILES = \
+	rtree-test-*.obj \
+	rtree-test-*.svg
+
+check_PROGRAMS = test-main test-bulkload
+
+test_main_SOURCES = \
+	test_main.cpp \
+	$(top_srcdir)/test/test_global.cpp
+
+test_main_SOURCES = \
+	test_basic.cpp \
+	test_copy.cpp \
+	test_directory_node_split.cpp \
+	test_erase_directories.cpp \
+	test_exact_search_by_extent.cpp \
+	test_exact_search_by_point.cpp \
+	test_forced_reinsertion.cpp \
+	test_geometry.cpp \
+	test_intersection.cpp \
+	test_main.cpp \
+	test_move.cpp \
+	test_node_split.cpp \
+	test_point_objects.cpp \
+	test_square_distance.cpp \
+	$(top_srcdir)/test/test_global.cpp
+
+test_bulkload_SOURCES = \
+	test_bulkload_main.cpp \
+	$(top_srcdir)/test/test_global.cpp
+
+EXTRA_DIST = test_global_rtree.hpp
+
+TESTS = test-main test-bulkload
+
+@VALGRIND_CHECK_RULES@
diff --git a/test/rtree/Makefile.in b/test/rtree/Makefile.in
new file mode 100644
index 0000000..429699f
--- /dev/null
+++ b/test/rtree/Makefile.in
@@ -0,0 +1,1089 @@
+# Makefile.in generated by automake 1.16.5 from Makefile.am.
+# @configure_input@
+
+# Copyright (C) 1994-2021 Free Software Foundation, Inc.
+
+# This Makefile.in is free software; the Free Software Foundation
+# gives unlimited permission to copy and/or distribute it,
+# with or without modifications, as long as this notice is preserved.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY, to the extent permitted by law; without
+# even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE.
+
+@SET_MAKE@
+VPATH = @srcdir@
+am__is_gnu_make = { \
+  if test -z '$(MAKELEVEL)'; then \
+    false; \
+  elif test -n '$(MAKE_HOST)'; then \
+    true; \
+  elif test -n '$(MAKE_VERSION)' && test -n '$(CURDIR)'; then \
+    true; \
+  else \
+    false; \
+  fi; \
+}
+am__make_running_with_option = \
+  case $${target_option-} in \
+      ?) ;; \
+      *) echo "am__make_running_with_option: internal error: invalid" \
+              "target option '$${target_option-}' specified" >&2; \
+         exit 1;; \
+  esac; \
+  has_opt=no; \
+  sane_makeflags=$$MAKEFLAGS; \
+  if $(am__is_gnu_make); then \
+    sane_makeflags=$$MFLAGS; \
+  else \
+    case $$MAKEFLAGS in \
+      *\\[\ \	]*) \
+        bs=\\; \
+        sane_makeflags=`printf '%s\n' "$$MAKEFLAGS" \
+          | sed "s/$$bs$$bs[$$bs $$bs	]*//g"`;; \
+    esac; \
+  fi; \
+  skip_next=no; \
+  strip_trailopt () \
+  { \
+    flg=`printf '%s\n' "$$flg" | sed "s/$$1.*$$//"`; \
+  }; \
+  for flg in $$sane_makeflags; do \
+    test $$skip_next = yes && { skip_next=no; continue; }; \
+    case $$flg in \
+      *=*|--*) continue;; \
+        -*I) strip_trailopt 'I'; skip_next=yes;; \
+      -*I?*) strip_trailopt 'I';; \
+        -*O) strip_trailopt 'O'; skip_next=yes;; \
+      -*O?*) strip_trailopt 'O';; \
+        -*l) strip_trailopt 'l'; skip_next=yes;; \
+      -*l?*) strip_trailopt 'l';; \
+      -[dEDm]) skip_next=yes;; \
+      -[JT]) skip_next=yes;; \
+    esac; \
+    case $$flg in \
+      *$$target_option*) has_opt=yes; break;; \
+    esac; \
+  done; \
+  test $$has_opt = yes
+am__make_dryrun = (target_option=n; $(am__make_running_with_option))
+am__make_keepgoing = (target_option=k; $(am__make_running_with_option))
+pkgdatadir = $(datadir)/@PACKAGE@
+pkgincludedir = $(includedir)/@PACKAGE@
+pkglibdir = $(libdir)/@PACKAGE@
+pkglibexecdir = $(libexecdir)/@PACKAGE@
+am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd
+install_sh_DATA = $(install_sh) -c -m 644
+install_sh_PROGRAM = $(install_sh) -c
+install_sh_SCRIPT = $(install_sh) -c
+INSTALL_HEADER = $(INSTALL_DATA)
+transform = $(program_transform_name)
+NORMAL_INSTALL = :
+PRE_INSTALL = :
+POST_INSTALL = :
+NORMAL_UNINSTALL = :
+PRE_UNINSTALL = :
+POST_UNINSTALL = :
+check_PROGRAMS = test-main$(EXEEXT) test-bulkload$(EXEEXT)
+TESTS = test-main$(EXEEXT) test-bulkload$(EXEEXT)
+subdir = test/rtree
+ACLOCAL_M4 = $(top_srcdir)/aclocal.m4
+am__aclocal_m4_deps = $(top_srcdir)/m4/ax_cxx_compile_stdcxx.m4 \
+	$(top_srcdir)/m4/ax_cxx_compile_stdcxx_17.m4 \
+	$(top_srcdir)/m4/m4_ax_valgrind_check.m4 \
+	$(top_srcdir)/configure.ac
+am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \
+	$(ACLOCAL_M4)
+DIST_COMMON = $(srcdir)/Makefile.am $(am__DIST_COMMON)
+mkinstalldirs = $(install_sh) -d
+CONFIG_CLEAN_FILES =
+CONFIG_CLEAN_VPATH_FILES =
+am__dirstamp = $(am__leading_dot)dirstamp
+am_test_bulkload_OBJECTS = test_bulkload_main.$(OBJEXT) \
+	$(top_builddir)/test/test_global.$(OBJEXT)
+test_bulkload_OBJECTS = $(am_test_bulkload_OBJECTS)
+test_bulkload_LDADD = $(LDADD)
+am_test_main_OBJECTS = test_basic.$(OBJEXT) test_copy.$(OBJEXT) \
+	test_directory_node_split.$(OBJEXT) \
+	test_erase_directories.$(OBJEXT) \
+	test_exact_search_by_extent.$(OBJEXT) \
+	test_exact_search_by_point.$(OBJEXT) \
+	test_forced_reinsertion.$(OBJEXT) test_geometry.$(OBJEXT) \
+	test_intersection.$(OBJEXT) test_main.$(OBJEXT) \
+	test_move.$(OBJEXT) test_node_split.$(OBJEXT) \
+	test_point_objects.$(OBJEXT) test_square_distance.$(OBJEXT) \
+	$(top_builddir)/test/test_global.$(OBJEXT)
+test_main_OBJECTS = $(am_test_main_OBJECTS)
+test_main_LDADD = $(LDADD)
+AM_V_P = $(am__v_P_@AM_V@)
+am__v_P_ = $(am__v_P_@AM_DEFAULT_V@)
+am__v_P_0 = false
+am__v_P_1 = :
+AM_V_GEN = $(am__v_GEN_@AM_V@)
+am__v_GEN_ = $(am__v_GEN_@AM_DEFAULT_V@)
+am__v_GEN_0 = @echo "  GEN     " $@;
+am__v_GEN_1 = 
+AM_V_at = $(am__v_at_@AM_V@)
+am__v_at_ = $(am__v_at_@AM_DEFAULT_V@)
+am__v_at_0 = @
+am__v_at_1 = 
+DEFAULT_INCLUDES = -I.@am__isrc@
+depcomp = $(SHELL) $(top_srcdir)/depcomp
+am__maybe_remake_depfiles = depfiles
+am__depfiles_remade = $(top_builddir)/test/$(DEPDIR)/test_global.Po \
+	./$(DEPDIR)/test_basic.Po ./$(DEPDIR)/test_bulkload_main.Po \
+	./$(DEPDIR)/test_copy.Po \
+	./$(DEPDIR)/test_directory_node_split.Po \
+	./$(DEPDIR)/test_erase_directories.Po \
+	./$(DEPDIR)/test_exact_search_by_extent.Po \
+	./$(DEPDIR)/test_exact_search_by_point.Po \
+	./$(DEPDIR)/test_forced_reinsertion.Po \
+	./$(DEPDIR)/test_geometry.Po ./$(DEPDIR)/test_intersection.Po \
+	./$(DEPDIR)/test_main.Po ./$(DEPDIR)/test_move.Po \
+	./$(DEPDIR)/test_node_split.Po \
+	./$(DEPDIR)/test_point_objects.Po \
+	./$(DEPDIR)/test_square_distance.Po
+am__mv = mv -f
+CXXCOMPILE = $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) \
+	$(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS)
+AM_V_CXX = $(am__v_CXX_@AM_V@)
+am__v_CXX_ = $(am__v_CXX_@AM_DEFAULT_V@)
+am__v_CXX_0 = @echo "  CXX     " $@;
+am__v_CXX_1 = 
+CXXLD = $(CXX)
+CXXLINK = $(CXXLD) $(AM_CXXFLAGS) $(CXXFLAGS) $(AM_LDFLAGS) $(LDFLAGS) \
+	-o $@
+AM_V_CXXLD = $(am__v_CXXLD_@AM_V@)
+am__v_CXXLD_ = $(am__v_CXXLD_@AM_DEFAULT_V@)
+am__v_CXXLD_0 = @echo "  CXXLD   " $@;
+am__v_CXXLD_1 = 
+SOURCES = $(test_bulkload_SOURCES) $(test_main_SOURCES)
+DIST_SOURCES = $(test_bulkload_SOURCES) $(test_main_SOURCES)
+am__can_run_installinfo = \
+  case $$AM_UPDATE_INFO_DIR in \
+    n|no|NO) false;; \
+    *) (install-info --version) >/dev/null 2>&1;; \
+  esac
+am__extra_recursive_targets = check-valgrind-recursive \
+	check-valgrind-memcheck-recursive \
+	check-valgrind-helgrind-recursive check-valgrind-drd-recursive \
+	check-valgrind-sgcheck-recursive
+am__tagged_files = $(HEADERS) $(SOURCES) $(TAGS_FILES) $(LISP)
+# Read a list of newline-separated strings from the standard input,
+# and print each of them once, without duplicates.  Input order is
+# *not* preserved.
+am__uniquify_input = $(AWK) '\
+  BEGIN { nonempty = 0; } \
+  { items[$$0] = 1; nonempty = 1; } \
+  END { if (nonempty) { for (i in items) print i; }; } \
+'
+# Make sure the list of sources is unique.  This is necessary because,
+# e.g., the same source file might be shared among _SOURCES variables
+# for different programs/libraries.
+am__define_uniq_tagged_files = \
+  list='$(am__tagged_files)'; \
+  unique=`for i in $$list; do \
+    if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
+  done | $(am__uniquify_input)`
+am__tty_colors_dummy = \
+  mgn= red= grn= lgn= blu= brg= std=; \
+  am__color_tests=no
+am__tty_colors = { \
+  $(am__tty_colors_dummy); \
+  if test "X$(AM_COLOR_TESTS)" = Xno; then \
+    am__color_tests=no; \
+  elif test "X$(AM_COLOR_TESTS)" = Xalways; then \
+    am__color_tests=yes; \
+  elif test "X$$TERM" != Xdumb && { test -t 1; } 2>/dev/null; then \
+    am__color_tests=yes; \
+  fi; \
+  if test $$am__color_tests = yes; then \
+    red=''; \
+    grn=''; \
+    lgn=''; \
+    blu=''; \
+    mgn=''; \
+    brg=''; \
+    std=''; \
+  fi; \
+}
+am__vpath_adj_setup = srcdirstrip=`echo "$(srcdir)" | sed 's|.|.|g'`;
+am__vpath_adj = case $$p in \
+    $(srcdir)/*) f=`echo "$$p" | sed "s|^$$srcdirstrip/||"`;; \
+    *) f=$$p;; \
+  esac;
+am__strip_dir = f=`echo $$p | sed -e 's|^.*/||'`;
+am__install_max = 40
+am__nobase_strip_setup = \
+  srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*|]/\\\\&/g'`
+am__nobase_strip = \
+  for p in $$list; do echo "$$p"; done | sed -e "s|$$srcdirstrip/||"
+am__nobase_list = $(am__nobase_strip_setup); \
+  for p in $$list; do echo "$$p $$p"; done | \
+  sed "s| $$srcdirstrip/| |;"' / .*\//!s/ .*/ ./; s,\( .*\)/[^/]*$$,\1,' | \
+  $(AWK) 'BEGIN { files["."] = "" } { files[$$2] = files[$$2] " " $$1; \
+    if (++n[$$2] == $(am__install_max)) \
+      { print $$2, files[$$2]; n[$$2] = 0; files[$$2] = "" } } \
+    END { for (dir in files) print dir, files[dir] }'
+am__base_list = \
+  sed '$$!N;$$!N;$$!N;$$!N;$$!N;$$!N;$$!N;s/\n/ /g' | \
+  sed '$$!N;$$!N;$$!N;$$!N;s/\n/ /g'
+am__uninstall_files_from_dir = { \
+  test -z "$$files" \
+    || { test ! -d "$$dir" && test ! -f "$$dir" && test ! -r "$$dir"; } \
+    || { echo " ( cd '$$dir' && rm -f" $$files ")"; \
+         $(am__cd) "$$dir" && rm -f $$files; }; \
+  }
+am__recheck_rx = ^[ 	]*:recheck:[ 	]*
+am__global_test_result_rx = ^[ 	]*:global-test-result:[ 	]*
+am__copy_in_global_log_rx = ^[ 	]*:copy-in-global-log:[ 	]*
+# A command that, given a newline-separated list of test names on the
+# standard input, print the name of the tests that are to be re-run
+# upon "make recheck".
+am__list_recheck_tests = $(AWK) '{ \
+  recheck = 1; \
+  while ((rc = (getline line < ($$0 ".trs"))) != 0) \
+    { \
+      if (rc < 0) \
+        { \
+          if ((getline line2 < ($$0 ".log")) < 0) \
+	    recheck = 0; \
+          break; \
+        } \
+      else if (line ~ /$(am__recheck_rx)[nN][Oo]/) \
+        { \
+          recheck = 0; \
+          break; \
+        } \
+      else if (line ~ /$(am__recheck_rx)[yY][eE][sS]/) \
+        { \
+          break; \
+        } \
+    }; \
+  if (recheck) \
+    print $$0; \
+  close ($$0 ".trs"); \
+  close ($$0 ".log"); \
+}'
+# A command that, given a newline-separated list of test names on the
+# standard input, create the global log from their .trs and .log files.
+am__create_global_log = $(AWK) ' \
+function fatal(msg) \
+{ \
+  print "fatal: making $@: " msg | "cat >&2"; \
+  exit 1; \
+} \
+function rst_section(header) \
+{ \
+  print header; \
+  len = length(header); \
+  for (i = 1; i <= len; i = i + 1) \
+    printf "="; \
+  printf "\n\n"; \
+} \
+{ \
+  copy_in_global_log = 1; \
+  global_test_result = "RUN"; \
+  while ((rc = (getline line < ($$0 ".trs"))) != 0) \
+    { \
+      if (rc < 0) \
+         fatal("failed to read from " $$0 ".trs"); \
+      if (line ~ /$(am__global_test_result_rx)/) \
+        { \
+          sub("$(am__global_test_result_rx)", "", line); \
+          sub("[ 	]*$$", "", line); \
+          global_test_result = line; \
+        } \
+      else if (line ~ /$(am__copy_in_global_log_rx)[nN][oO]/) \
+        copy_in_global_log = 0; \
+    }; \
+  if (copy_in_global_log) \
+    { \
+      rst_section(global_test_result ": " $$0); \
+      while ((rc = (getline line < ($$0 ".log"))) != 0) \
+      { \
+        if (rc < 0) \
+          fatal("failed to read from " $$0 ".log"); \
+        print line; \
+      }; \
+      printf "\n"; \
+    }; \
+  close ($$0 ".trs"); \
+  close ($$0 ".log"); \
+}'
+# Restructured Text title.
+am__rst_title = { sed 's/.*/   &   /;h;s/./=/g;p;x;s/ *$$//;p;g' && echo; }
+# Solaris 10 'make', and several other traditional 'make' implementations,
+# pass "-e" to $(SHELL), and POSIX 2008 even requires this.  Work around it
+# by disabling -e (using the XSI extension "set +e") if it's set.
+am__sh_e_setup = case $$- in *e*) set +e;; esac
+# Default flags passed to test drivers.
+am__common_driver_flags = \
+  --color-tests "$$am__color_tests" \
+  --enable-hard-errors "$$am__enable_hard_errors" \
+  --expect-failure "$$am__expect_failure"
+# To be inserted before the command running the test.  Creates the
+# directory for the log if needed.  Stores in $dir the directory
+# containing $f, in $tst the test, in $log the log.  Executes the
+# developer- defined test setup AM_TESTS_ENVIRONMENT (if any), and
+# passes TESTS_ENVIRONMENT.  Set up options for the wrapper that
+# will run the test scripts (or their associated LOG_COMPILER, if
+# thy have one).
+am__check_pre = \
+$(am__sh_e_setup);					\
+$(am__vpath_adj_setup) $(am__vpath_adj)			\
+$(am__tty_colors);					\
+srcdir=$(srcdir); export srcdir;			\
+case "$@" in						\
+  */*) am__odir=`echo "./$@" | sed 's|/[^/]*$$||'`;;	\
+    *) am__odir=.;; 					\
+esac;							\
+test "x$$am__odir" = x"." || test -d "$$am__odir" 	\
+  || $(MKDIR_P) "$$am__odir" || exit $$?;		\
+if test -f "./$$f"; then dir=./;			\
+elif test -f "$$f"; then dir=;				\
+else dir="$(srcdir)/"; fi;				\
+tst=$$dir$$f; log='$@'; 				\
+if test -n '$(DISABLE_HARD_ERRORS)'; then		\
+  am__enable_hard_errors=no; 				\
+else							\
+  am__enable_hard_errors=yes; 				\
+fi; 							\
+case " $(XFAIL_TESTS) " in				\
+  *[\ \	]$$f[\ \	]* | *[\ \	]$$dir$$f[\ \	]*) \
+    am__expect_failure=yes;;				\
+  *)							\
+    am__expect_failure=no;;				\
+esac; 							\
+$(AM_TESTS_ENVIRONMENT) $(TESTS_ENVIRONMENT)
+# A shell command to get the names of the tests scripts with any registered
+# extension removed (i.e., equivalently, the names of the test logs, with
+# the '.log' extension removed).  The result is saved in the shell variable
+# '$bases'.  This honors runtime overriding of TESTS and TEST_LOGS.  Sadly,
+# we cannot use something simpler, involving e.g., "$(TEST_LOGS:.log=)",
+# since that might cause problem with VPATH rewrites for suffix-less tests.
+# See also 'test-harness-vpath-rewrite.sh' and 'test-trs-basic.sh'.
+am__set_TESTS_bases = \
+  bases='$(TEST_LOGS)'; \
+  bases=`for i in $$bases; do echo $$i; done | sed 's/\.log$$//'`; \
+  bases=`echo $$bases`
+AM_TESTSUITE_SUMMARY_HEADER = ' for $(PACKAGE_STRING)'
+RECHECK_LOGS = $(TEST_LOGS)
+AM_RECURSIVE_TARGETS = check recheck
+TEST_SUITE_LOG = test-suite.log
+TEST_EXTENSIONS = @EXEEXT@ .test
+LOG_DRIVER = $(SHELL) $(top_srcdir)/test-driver
+LOG_COMPILE = $(LOG_COMPILER) $(AM_LOG_FLAGS) $(LOG_FLAGS)
+am__set_b = \
+  case '$@' in \
+    */*) \
+      case '$*' in \
+        */*) b='$*';; \
+          *) b=`echo '$@' | sed 's/\.log$$//'`; \
+       esac;; \
+    *) \
+      b='$*';; \
+  esac
+am__test_logs1 = $(TESTS:=.log)
+am__test_logs2 = $(am__test_logs1:@EXEEXT@.log=.log)
+TEST_LOGS = $(am__test_logs2:.test.log=.log)
+TEST_LOG_DRIVER = $(SHELL) $(top_srcdir)/test-driver
+TEST_LOG_COMPILE = $(TEST_LOG_COMPILER) $(AM_TEST_LOG_FLAGS) \
+	$(TEST_LOG_FLAGS)
+am__DIST_COMMON = $(srcdir)/Makefile.in $(top_srcdir)/depcomp \
+	$(top_srcdir)/test-driver
+DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST)
+ACLOCAL = @ACLOCAL@
+AMTAR = @AMTAR@
+AM_DEFAULT_VERBOSITY = @AM_DEFAULT_VERBOSITY@
+API_VERSION = @API_VERSION@
+AUTOCONF = @AUTOCONF@
+AUTOHEADER = @AUTOHEADER@
+AUTOMAKE = @AUTOMAKE@
+AWK = @AWK@
+CC = @CC@
+CCDEPMODE = @CCDEPMODE@
+CFLAGS = @CFLAGS@
+CPPFLAGS = @CPPFLAGS@
+CPPFLAGS_NODEBUG = @CPPFLAGS_NODEBUG@
+CSCOPE = @CSCOPE@
+CTAGS = @CTAGS@
+CXX = @CXX@
+CXXDEPMODE = @CXXDEPMODE@
+CXXFLAGS = @CXXFLAGS@
+CXXFLAGS_UNITTESTS = @CXXFLAGS_UNITTESTS@
+CYGPATH_W = @CYGPATH_W@
+DEFS = @DEFS@
+DEPDIR = @DEPDIR@
+DOXYGEN = @DOXYGEN@
+ECHO_C = @ECHO_C@
+ECHO_N = @ECHO_N@
+ECHO_T = @ECHO_T@
+ENABLE_VALGRIND_drd = @ENABLE_VALGRIND_drd@
+ENABLE_VALGRIND_helgrind = @ENABLE_VALGRIND_helgrind@
+ENABLE_VALGRIND_memcheck = @ENABLE_VALGRIND_memcheck@
+ENABLE_VALGRIND_sgcheck = @ENABLE_VALGRIND_sgcheck@
+ETAGS = @ETAGS@
+EXEEXT = @EXEEXT@
+EXPECT = @EXPECT@
+GDB = @GDB@
+HAVE_CXX17 = @HAVE_CXX17@
+INCDIR = @INCDIR@
+INSTALL = @INSTALL@
+INSTALL_DATA = @INSTALL_DATA@
+INSTALL_PROGRAM = @INSTALL_PROGRAM@
+INSTALL_SCRIPT = @INSTALL_SCRIPT@
+INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@
+LDFLAGS = @LDFLAGS@
+LIBOBJS = @LIBOBJS@
+LIBS = @LIBS@
+LTLIBOBJS = @LTLIBOBJS@
+MAINT = @MAINT@
+MAKEINFO = @MAKEINFO@
+MISCDIR = @MISCDIR@
+MKDIR_P = @MKDIR_P@
+OBJDIR = @OBJDIR@
+OBJEXT = @OBJEXT@
+PACKAGE = @PACKAGE@
+PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@
+PACKAGE_NAME = @PACKAGE_NAME@
+PACKAGE_STRING = @PACKAGE_STRING@
+PACKAGE_TARNAME = @PACKAGE_TARNAME@
+PACKAGE_URL = @PACKAGE_URL@
+PACKAGE_VERSION = @PACKAGE_VERSION@
+PATH_SEPARATOR = @PATH_SEPARATOR@
+QUICKCHECKDIR = @QUICKCHECKDIR@
+RUNTEST_BIN = @RUNTEST_BIN@
+SET_MAKE = @SET_MAKE@
+SHELL = @SHELL@
+SPHINX = @SPHINX@
+STRIP = @STRIP@
+VALGRIND = @VALGRIND@
+VALGRIND_ENABLED = @VALGRIND_ENABLED@
+VERSION = @VERSION@
+abs_builddir = @abs_builddir@
+abs_srcdir = @abs_srcdir@
+abs_top_builddir = @abs_top_builddir@
+abs_top_srcdir = @abs_top_srcdir@
+ac_ct_CC = @ac_ct_CC@
+ac_ct_CXX = @ac_ct_CXX@
+am__include = @am__include@
+am__leading_dot = @am__leading_dot@
+am__quote = @am__quote@
+am__tar = @am__tar@
+am__untar = @am__untar@
+bindir = @bindir@
+build_alias = @build_alias@
+builddir = @builddir@
+datadir = @datadir@
+datarootdir = @datarootdir@
+docdir = @docdir@
+dvidir = @dvidir@
+exec_prefix = @exec_prefix@
+host_alias = @host_alias@
+htmldir = @htmldir@
+includedir = @includedir@
+infodir = @infodir@
+install_sh = @install_sh@
+libdir = @libdir@
+libexecdir = @libexecdir@
+localedir = @localedir@
+localstatedir = @localstatedir@
+mandir = @mandir@
+mkdir_p = @mkdir_p@
+oldincludedir = @oldincludedir@
+pdfdir = @pdfdir@
+prefix = @prefix@
+program_transform_name = @program_transform_name@
+psdir = @psdir@
+runstatedir = @runstatedir@
+sbindir = @sbindir@
+sharedstatedir = @sharedstatedir@
+srcdir = @srcdir@
+sysconfdir = @sysconfdir@
+target_alias = @target_alias@
+top_build_prefix = @top_build_prefix@
+top_builddir = @top_builddir@
+top_srcdir = @top_srcdir@
+valgrind_enabled_tools = @valgrind_enabled_tools@
+valgrind_tools = @valgrind_tools@
+AM_CPPFLAGS = \
+	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/test/include \
+	$(CXXFLAGS_UNITTESTS)
+
+DISTCLEANFILES = \
+	rtree-test-*.obj \
+	rtree-test-*.svg
+
+test_main_SOURCES = \
+	test_basic.cpp \
+	test_copy.cpp \
+	test_directory_node_split.cpp \
+	test_erase_directories.cpp \
+	test_exact_search_by_extent.cpp \
+	test_exact_search_by_point.cpp \
+	test_forced_reinsertion.cpp \
+	test_geometry.cpp \
+	test_intersection.cpp \
+	test_main.cpp \
+	test_move.cpp \
+	test_node_split.cpp \
+	test_point_objects.cpp \
+	test_square_distance.cpp \
+	$(top_srcdir)/test/test_global.cpp
+
+test_bulkload_SOURCES = \
+	test_bulkload_main.cpp \
+	$(top_srcdir)/test/test_global.cpp
+
+EXTRA_DIST = test_global_rtree.hpp
+all: all-am
+
+.SUFFIXES:
+.SUFFIXES: .cpp .log .o .obj .test .test$(EXEEXT) .trs
+$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.am  $(am__configure_deps)
+	@for dep in $?; do \
+	  case '$(am__configure_deps)' in \
+	    *$$dep*) \
+	      ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \
+	        && { if test -f $@; then exit 0; else break; fi; }; \
+	      exit 1;; \
+	  esac; \
+	done; \
+	echo ' cd $(top_srcdir) && $(AUTOMAKE) --foreign test/rtree/Makefile'; \
+	$(am__cd) $(top_srcdir) && \
+	  $(AUTOMAKE) --foreign test/rtree/Makefile
+Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status
+	@case '$?' in \
+	  *config.status*) \
+	    cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \
+	  *) \
+	    echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__maybe_remake_depfiles)'; \
+	    cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__maybe_remake_depfiles);; \
+	esac;
+
+$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES)
+	cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
+
+$(top_srcdir)/configure: @MAINTAINER_MODE_TRUE@ $(am__configure_deps)
+	cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
+$(ACLOCAL_M4): @MAINTAINER_MODE_TRUE@ $(am__aclocal_m4_deps)
+	cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
+$(am__aclocal_m4_deps):
+
+clean-checkPROGRAMS:
+	-test -z "$(check_PROGRAMS)" || rm -f $(check_PROGRAMS)
+$(top_builddir)/test/$(am__dirstamp):
+	@$(MKDIR_P) $(top_builddir)/test
+	@: > $(top_builddir)/test/$(am__dirstamp)
+$(top_builddir)/test/$(DEPDIR)/$(am__dirstamp):
+	@$(MKDIR_P) $(top_builddir)/test/$(DEPDIR)
+	@: > $(top_builddir)/test/$(DEPDIR)/$(am__dirstamp)
+$(top_builddir)/test/test_global.$(OBJEXT):  \
+	$(top_builddir)/test/$(am__dirstamp) \
+	$(top_builddir)/test/$(DEPDIR)/$(am__dirstamp)
+
+test-bulkload$(EXEEXT): $(test_bulkload_OBJECTS) $(test_bulkload_DEPENDENCIES) $(EXTRA_test_bulkload_DEPENDENCIES) 
+	@rm -f test-bulkload$(EXEEXT)
+	$(AM_V_CXXLD)$(CXXLINK) $(test_bulkload_OBJECTS) $(test_bulkload_LDADD) $(LIBS)
+
+test-main$(EXEEXT): $(test_main_OBJECTS) $(test_main_DEPENDENCIES) $(EXTRA_test_main_DEPENDENCIES) 
+	@rm -f test-main$(EXEEXT)
+	$(AM_V_CXXLD)$(CXXLINK) $(test_main_OBJECTS) $(test_main_LDADD) $(LIBS)
+
+mostlyclean-compile:
+	-rm -f *.$(OBJEXT)
+	-rm -f $(top_builddir)/test/*.$(OBJEXT)
+
+distclean-compile:
+	-rm -f *.tab.c
+
+@AMDEP_TRUE@@am__include@ @am__quote@$(top_builddir)/test/$(DEPDIR)/test_global.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_basic.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_bulkload_main.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_copy.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_directory_node_split.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_erase_directories.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_exact_search_by_extent.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_exact_search_by_point.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_forced_reinsertion.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_geometry.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_intersection.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_main.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_move.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_node_split.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_point_objects.Po@am__quote@ # am--include-marker
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/test_square_distance.Po@am__quote@ # am--include-marker
+
+$(am__depfiles_remade):
+	@$(MKDIR_P) $(@D)
+	@echo '# dummy' >$@-t && $(am__mv) $@-t $@
+
+am--depfiles: $(am__depfiles_remade)
+
+.cpp.o:
+@am__fastdepCXX_TRUE@	$(AM_V_CXX)depbase=`echo $@ | sed 's|[^/]*$$|$(DEPDIR)/&|;s|\.o$$||'`;\
+@am__fastdepCXX_TRUE@	$(CXXCOMPILE) -MT $@ -MD -MP -MF $$depbase.Tpo -c -o $@ $< &&\
+@am__fastdepCXX_TRUE@	$(am__mv) $$depbase.Tpo $$depbase.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	$(AM_V_CXX)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@	$(AM_V_CXX@am__nodep@)$(CXXCOMPILE) -c -o $@ $<
+
+.cpp.obj:
+@am__fastdepCXX_TRUE@	$(AM_V_CXX)depbase=`echo $@ | sed 's|[^/]*$$|$(DEPDIR)/&|;s|\.obj$$||'`;\
+@am__fastdepCXX_TRUE@	$(CXXCOMPILE) -MT $@ -MD -MP -MF $$depbase.Tpo -c -o $@ `$(CYGPATH_W) '$<'` &&\
+@am__fastdepCXX_TRUE@	$(am__mv) $$depbase.Tpo $$depbase.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	$(AM_V_CXX)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@	$(AM_V_CXX@am__nodep@)$(CXXCOMPILE) -c -o $@ `$(CYGPATH_W) '$<'`
+check-valgrind-local: 
+check-valgrind-memcheck-local: 
+check-valgrind-helgrind-local: 
+check-valgrind-drd-local: 
+check-valgrind-sgcheck-local: 
+
+ID: $(am__tagged_files)
+	$(am__define_uniq_tagged_files); mkid -fID $$unique
+tags: tags-am
+TAGS: tags
+
+tags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files)
+	set x; \
+	here=`pwd`; \
+	$(am__define_uniq_tagged_files); \
+	shift; \
+	if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \
+	  test -n "$$unique" || unique=$$empty_fix; \
+	  if test $$# -gt 0; then \
+	    $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \
+	      "$$@" $$unique; \
+	  else \
+	    $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \
+	      $$unique; \
+	  fi; \
+	fi
+ctags: ctags-am
+
+CTAGS: ctags
+ctags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files)
+	$(am__define_uniq_tagged_files); \
+	test -z "$(CTAGS_ARGS)$$unique" \
+	  || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \
+	     $$unique
+
+GTAGS:
+	here=`$(am__cd) $(top_builddir) && pwd` \
+	  && $(am__cd) $(top_srcdir) \
+	  && gtags -i $(GTAGS_ARGS) "$$here"
+cscopelist: cscopelist-am
+
+cscopelist-am: $(am__tagged_files)
+	list='$(am__tagged_files)'; \
+	case "$(srcdir)" in \
+	  [\\/]* | ?:[\\/]*) sdir="$(srcdir)" ;; \
+	  *) sdir=$(subdir)/$(srcdir) ;; \
+	esac; \
+	for i in $$list; do \
+	  if test -f "$$i"; then \
+	    echo "$(subdir)/$$i"; \
+	  else \
+	    echo "$$sdir/$$i"; \
+	  fi; \
+	done >> $(top_builddir)/cscope.files
+
+distclean-tags:
+	-rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags
+
+# Recover from deleted '.trs' file; this should ensure that
+# "rm -f foo.log; make foo.trs" re-run 'foo.test', and re-create
+# both 'foo.log' and 'foo.trs'.  Break the recipe in two subshells
+# to avoid problems with "make -n".
+.log.trs:
+	rm -f $< $@
+	$(MAKE) $(AM_MAKEFLAGS) $<
+
+# Leading 'am--fnord' is there to ensure the list of targets does not
+# expand to empty, as could happen e.g. with make check TESTS=''.
+am--fnord $(TEST_LOGS) $(TEST_LOGS:.log=.trs): $(am__force_recheck)
+am--force-recheck:
+	@:
+
+$(TEST_SUITE_LOG): $(TEST_LOGS)
+	@$(am__set_TESTS_bases); \
+	am__f_ok () { test -f "$$1" && test -r "$$1"; }; \
+	redo_bases=`for i in $$bases; do \
+	              am__f_ok $$i.trs && am__f_ok $$i.log || echo $$i; \
+	            done`; \
+	if test -n "$$redo_bases"; then \
+	  redo_logs=`for i in $$redo_bases; do echo $$i.log; done`; \
+	  redo_results=`for i in $$redo_bases; do echo $$i.trs; done`; \
+	  if $(am__make_dryrun); then :; else \
+	    rm -f $$redo_logs && rm -f $$redo_results || exit 1; \
+	  fi; \
+	fi; \
+	if test -n "$$am__remaking_logs"; then \
+	  echo "fatal: making $(TEST_SUITE_LOG): possible infinite" \
+	       "recursion detected" >&2; \
+	elif test -n "$$redo_logs"; then \
+	  am__remaking_logs=yes $(MAKE) $(AM_MAKEFLAGS) $$redo_logs; \
+	fi; \
+	if $(am__make_dryrun); then :; else \
+	  st=0;  \
+	  errmsg="fatal: making $(TEST_SUITE_LOG): failed to create"; \
+	  for i in $$redo_bases; do \
+	    test -f $$i.trs && test -r $$i.trs \
+	      || { echo "$$errmsg $$i.trs" >&2; st=1; }; \
+	    test -f $$i.log && test -r $$i.log \
+	      || { echo "$$errmsg $$i.log" >&2; st=1; }; \
+	  done; \
+	  test $$st -eq 0 || exit 1; \
+	fi
+	@$(am__sh_e_setup); $(am__tty_colors); $(am__set_TESTS_bases); \
+	ws='[ 	]'; \
+	results=`for b in $$bases; do echo $$b.trs; done`; \
+	test -n "$$results" || results=/dev/null; \
+	all=`  grep "^$$ws*:test-result:"           $$results | wc -l`; \
+	pass=` grep "^$$ws*:test-result:$$ws*PASS"  $$results | wc -l`; \
+	fail=` grep "^$$ws*:test-result:$$ws*FAIL"  $$results | wc -l`; \
+	skip=` grep "^$$ws*:test-result:$$ws*SKIP"  $$results | wc -l`; \
+	xfail=`grep "^$$ws*:test-result:$$ws*XFAIL" $$results | wc -l`; \
+	xpass=`grep "^$$ws*:test-result:$$ws*XPASS" $$results | wc -l`; \
+	error=`grep "^$$ws*:test-result:$$ws*ERROR" $$results | wc -l`; \
+	if test `expr $$fail + $$xpass + $$error` -eq 0; then \
+	  success=true; \
+	else \
+	  success=false; \
+	fi; \
+	br='==================='; br=$$br$$br$$br$$br; \
+	result_count () \
+	{ \
+	    if test x"$$1" = x"--maybe-color"; then \
+	      maybe_colorize=yes; \
+	    elif test x"$$1" = x"--no-color"; then \
+	      maybe_colorize=no; \
+	    else \
+	      echo "$@: invalid 'result_count' usage" >&2; exit 4; \
+	    fi; \
+	    shift; \
+	    desc=$$1 count=$$2; \
+	    if test $$maybe_colorize = yes && test $$count -gt 0; then \
+	      color_start=$$3 color_end=$$std; \
+	    else \
+	      color_start= color_end=; \
+	    fi; \
+	    echo "$${color_start}# $$desc $$count$${color_end}"; \
+	}; \
+	create_testsuite_report () \
+	{ \
+	  result_count $$1 "TOTAL:" $$all   "$$brg"; \
+	  result_count $$1 "PASS: " $$pass  "$$grn"; \
+	  result_count $$1 "SKIP: " $$skip  "$$blu"; \
+	  result_count $$1 "XFAIL:" $$xfail "$$lgn"; \
+	  result_count $$1 "FAIL: " $$fail  "$$red"; \
+	  result_count $$1 "XPASS:" $$xpass "$$red"; \
+	  result_count $$1 "ERROR:" $$error "$$mgn"; \
+	}; \
+	{								\
+	  echo "$(PACKAGE_STRING): $(subdir)/$(TEST_SUITE_LOG)" |	\
+	    $(am__rst_title);						\
+	  create_testsuite_report --no-color;				\
+	  echo;								\
+	  echo ".. contents:: :depth: 2";				\
+	  echo;								\
+	  for b in $$bases; do echo $$b; done				\
+	    | $(am__create_global_log);					\
+	} >$(TEST_SUITE_LOG).tmp || exit 1;				\
+	mv $(TEST_SUITE_LOG).tmp $(TEST_SUITE_LOG);			\
+	if $$success; then						\
+	  col="$$grn";							\
+	 else								\
+	  col="$$red";							\
+	  test x"$$VERBOSE" = x || cat $(TEST_SUITE_LOG);		\
+	fi;								\
+	echo "$${col}$$br$${std}"; 					\
+	echo "$${col}Testsuite summary"$(AM_TESTSUITE_SUMMARY_HEADER)"$${std}";	\
+	echo "$${col}$$br$${std}"; 					\
+	create_testsuite_report --maybe-color;				\
+	echo "$$col$$br$$std";						\
+	if $$success; then :; else					\
+	  echo "$${col}See $(subdir)/$(TEST_SUITE_LOG)$${std}";		\
+	  if test -n "$(PACKAGE_BUGREPORT)"; then			\
+	    echo "$${col}Please report to $(PACKAGE_BUGREPORT)$${std}";	\
+	  fi;								\
+	  echo "$$col$$br$$std";					\
+	fi;								\
+	$$success || exit 1
+
+check-TESTS: $(check_PROGRAMS)
+	@list='$(RECHECK_LOGS)';           test -z "$$list" || rm -f $$list
+	@list='$(RECHECK_LOGS:.log=.trs)'; test -z "$$list" || rm -f $$list
+	@test -z "$(TEST_SUITE_LOG)" || rm -f $(TEST_SUITE_LOG)
+	@set +e; $(am__set_TESTS_bases); \
+	log_list=`for i in $$bases; do echo $$i.log; done`; \
+	trs_list=`for i in $$bases; do echo $$i.trs; done`; \
+	log_list=`echo $$log_list`; trs_list=`echo $$trs_list`; \
+	$(MAKE) $(AM_MAKEFLAGS) $(TEST_SUITE_LOG) TEST_LOGS="$$log_list"; \
+	exit $$?;
+recheck: all $(check_PROGRAMS)
+	@test -z "$(TEST_SUITE_LOG)" || rm -f $(TEST_SUITE_LOG)
+	@set +e; $(am__set_TESTS_bases); \
+	bases=`for i in $$bases; do echo $$i; done \
+	         | $(am__list_recheck_tests)` || exit 1; \
+	log_list=`for i in $$bases; do echo $$i.log; done`; \
+	log_list=`echo $$log_list`; \
+	$(MAKE) $(AM_MAKEFLAGS) $(TEST_SUITE_LOG) \
+	        am__force_recheck=am--force-recheck \
+	        TEST_LOGS="$$log_list"; \
+	exit $$?
+test-main.log: test-main$(EXEEXT)
+	@p='test-main$(EXEEXT)'; \
+	b='test-main'; \
+	$(am__check_pre) $(LOG_DRIVER) --test-name "$$f" \
+	--log-file $$b.log --trs-file $$b.trs \
+	$(am__common_driver_flags) $(AM_LOG_DRIVER_FLAGS) $(LOG_DRIVER_FLAGS) -- $(LOG_COMPILE) \
+	"$$tst" $(AM_TESTS_FD_REDIRECT)
+test-bulkload.log: test-bulkload$(EXEEXT)
+	@p='test-bulkload$(EXEEXT)'; \
+	b='test-bulkload'; \
+	$(am__check_pre) $(LOG_DRIVER) --test-name "$$f" \
+	--log-file $$b.log --trs-file $$b.trs \
+	$(am__common_driver_flags) $(AM_LOG_DRIVER_FLAGS) $(LOG_DRIVER_FLAGS) -- $(LOG_COMPILE) \
+	"$$tst" $(AM_TESTS_FD_REDIRECT)
+.test.log:
+	@p='$<'; \
+	$(am__set_b); \
+	$(am__check_pre) $(TEST_LOG_DRIVER) --test-name "$$f" \
+	--log-file $$b.log --trs-file $$b.trs \
+	$(am__common_driver_flags) $(AM_TEST_LOG_DRIVER_FLAGS) $(TEST_LOG_DRIVER_FLAGS) -- $(TEST_LOG_COMPILE) \
+	"$$tst" $(AM_TESTS_FD_REDIRECT)
+@am__EXEEXT_TRUE@.test$(EXEEXT).log:
+@am__EXEEXT_TRUE@	@p='$<'; \
+@am__EXEEXT_TRUE@	$(am__set_b); \
+@am__EXEEXT_TRUE@	$(am__check_pre) $(TEST_LOG_DRIVER) --test-name "$$f" \
+@am__EXEEXT_TRUE@	--log-file $$b.log --trs-file $$b.trs \
+@am__EXEEXT_TRUE@	$(am__common_driver_flags) $(AM_TEST_LOG_DRIVER_FLAGS) $(TEST_LOG_DRIVER_FLAGS) -- $(TEST_LOG_COMPILE) \
+@am__EXEEXT_TRUE@	"$$tst" $(AM_TESTS_FD_REDIRECT)
+distdir: $(BUILT_SOURCES)
+	$(MAKE) $(AM_MAKEFLAGS) distdir-am
+
+distdir-am: $(DISTFILES)
+	@srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \
+	topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \
+	list='$(DISTFILES)'; \
+	  dist_files=`for file in $$list; do echo $$file; done | \
+	  sed -e "s|^$$srcdirstrip/||;t" \
+	      -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \
+	case $$dist_files in \
+	  */*) $(MKDIR_P) `echo "$$dist_files" | \
+			   sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \
+			   sort -u` ;; \
+	esac; \
+	for file in $$dist_files; do \
+	  if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \
+	  if test -d $$d/$$file; then \
+	    dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \
+	    if test -d "$(distdir)/$$file"; then \
+	      find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \
+	    fi; \
+	    if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \
+	      cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \
+	      find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \
+	    fi; \
+	    cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \
+	  else \
+	    test -f "$(distdir)/$$file" \
+	    || cp -p $$d/$$file "$(distdir)/$$file" \
+	    || exit 1; \
+	  fi; \
+	done
+check-am: all-am
+	$(MAKE) $(AM_MAKEFLAGS) $(check_PROGRAMS)
+	$(MAKE) $(AM_MAKEFLAGS) check-TESTS
+check: check-am
+all-am: Makefile
+installdirs:
+install: install-am
+install-exec: install-exec-am
+install-data: install-data-am
+uninstall: uninstall-am
+
+install-am: all-am
+	@$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am
+
+installcheck: installcheck-am
+install-strip:
+	if test -z '$(STRIP)'; then \
+	  $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+	    install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
+	      install; \
+	else \
+	  $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+	    install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
+	    "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \
+	fi
+mostlyclean-generic:
+	-test -z "$(TEST_LOGS)" || rm -f $(TEST_LOGS)
+	-test -z "$(TEST_LOGS:.log=.trs)" || rm -f $(TEST_LOGS:.log=.trs)
+	-test -z "$(TEST_SUITE_LOG)" || rm -f $(TEST_SUITE_LOG)
+
+clean-generic:
+
+distclean-generic:
+	-test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES)
+	-test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES)
+	-test -z "$(DISTCLEANFILES)" || rm -f $(DISTCLEANFILES)
+	-test -z "$(top_builddir)/test/$(DEPDIR)/$(am__dirstamp)" || rm -f $(top_builddir)/test/$(DEPDIR)/$(am__dirstamp)
+	-test -z "$(top_builddir)/test/$(am__dirstamp)" || rm -f $(top_builddir)/test/$(am__dirstamp)
+
+maintainer-clean-generic:
+	@echo "This command is intended for maintainers to use"
+	@echo "it deletes files that may require special tools to rebuild."
+check-valgrind: check-valgrind-am
+
+check-valgrind-am: check-valgrind-local
+
+check-valgrind-drd: check-valgrind-drd-am
+
+check-valgrind-drd-am: check-valgrind-drd-local
+
+check-valgrind-helgrind: check-valgrind-helgrind-am
+
+check-valgrind-helgrind-am: check-valgrind-helgrind-local
+
+check-valgrind-memcheck: check-valgrind-memcheck-am
+
+check-valgrind-memcheck-am: check-valgrind-memcheck-local
+
+check-valgrind-sgcheck: check-valgrind-sgcheck-am
+
+check-valgrind-sgcheck-am: check-valgrind-sgcheck-local
+
+clean: clean-am
+
+clean-am: clean-checkPROGRAMS clean-generic mostlyclean-am
+
+distclean: distclean-am
+		-rm -f $(top_builddir)/test/$(DEPDIR)/test_global.Po
+	-rm -f ./$(DEPDIR)/test_basic.Po
+	-rm -f ./$(DEPDIR)/test_bulkload_main.Po
+	-rm -f ./$(DEPDIR)/test_copy.Po
+	-rm -f ./$(DEPDIR)/test_directory_node_split.Po
+	-rm -f ./$(DEPDIR)/test_erase_directories.Po
+	-rm -f ./$(DEPDIR)/test_exact_search_by_extent.Po
+	-rm -f ./$(DEPDIR)/test_exact_search_by_point.Po
+	-rm -f ./$(DEPDIR)/test_forced_reinsertion.Po
+	-rm -f ./$(DEPDIR)/test_geometry.Po
+	-rm -f ./$(DEPDIR)/test_intersection.Po
+	-rm -f ./$(DEPDIR)/test_main.Po
+	-rm -f ./$(DEPDIR)/test_move.Po
+	-rm -f ./$(DEPDIR)/test_node_split.Po
+	-rm -f ./$(DEPDIR)/test_point_objects.Po
+	-rm -f ./$(DEPDIR)/test_square_distance.Po
+	-rm -f Makefile
+distclean-am: clean-am distclean-compile distclean-generic \
+	distclean-tags
+
+dvi: dvi-am
+
+dvi-am:
+
+html: html-am
+
+html-am:
+
+info: info-am
+
+info-am:
+
+install-data-am:
+
+install-dvi: install-dvi-am
+
+install-dvi-am:
+
+install-exec-am:
+
+install-html: install-html-am
+
+install-html-am:
+
+install-info: install-info-am
+
+install-info-am:
+
+install-man:
+
+install-pdf: install-pdf-am
+
+install-pdf-am:
+
+install-ps: install-ps-am
+
+install-ps-am:
+
+installcheck-am:
+
+maintainer-clean: maintainer-clean-am
+		-rm -f $(top_builddir)/test/$(DEPDIR)/test_global.Po
+	-rm -f ./$(DEPDIR)/test_basic.Po
+	-rm -f ./$(DEPDIR)/test_bulkload_main.Po
+	-rm -f ./$(DEPDIR)/test_copy.Po
+	-rm -f ./$(DEPDIR)/test_directory_node_split.Po
+	-rm -f ./$(DEPDIR)/test_erase_directories.Po
+	-rm -f ./$(DEPDIR)/test_exact_search_by_extent.Po
+	-rm -f ./$(DEPDIR)/test_exact_search_by_point.Po
+	-rm -f ./$(DEPDIR)/test_forced_reinsertion.Po
+	-rm -f ./$(DEPDIR)/test_geometry.Po
+	-rm -f ./$(DEPDIR)/test_intersection.Po
+	-rm -f ./$(DEPDIR)/test_main.Po
+	-rm -f ./$(DEPDIR)/test_move.Po
+	-rm -f ./$(DEPDIR)/test_node_split.Po
+	-rm -f ./$(DEPDIR)/test_point_objects.Po
+	-rm -f ./$(DEPDIR)/test_square_distance.Po
+	-rm -f Makefile
+maintainer-clean-am: distclean-am maintainer-clean-generic
+
+mostlyclean: mostlyclean-am
+
+mostlyclean-am: mostlyclean-compile mostlyclean-generic
+
+pdf: pdf-am
+
+pdf-am:
+
+ps: ps-am
+
+ps-am:
+
+uninstall-am:
+
+.MAKE: check-am install-am install-strip
+
+.PHONY: CTAGS GTAGS TAGS all all-am am--depfiles check check-TESTS \
+	check-am check-valgrind-am check-valgrind-drd-am \
+	check-valgrind-drd-local check-valgrind-helgrind-am \
+	check-valgrind-helgrind-local check-valgrind-local \
+	check-valgrind-memcheck-am check-valgrind-memcheck-local \
+	check-valgrind-sgcheck-am check-valgrind-sgcheck-local clean \
+	clean-checkPROGRAMS clean-generic cscopelist-am ctags ctags-am \
+	distclean distclean-compile distclean-generic distclean-tags \
+	distdir dvi dvi-am html html-am info info-am install \
+	install-am install-data install-data-am install-dvi \
+	install-dvi-am install-exec install-exec-am install-html \
+	install-html-am install-info install-info-am install-man \
+	install-pdf install-pdf-am install-ps install-ps-am \
+	install-strip installcheck installcheck-am installdirs \
+	maintainer-clean maintainer-clean-generic mostlyclean \
+	mostlyclean-compile mostlyclean-generic pdf pdf-am ps ps-am \
+	recheck tags tags-am uninstall uninstall-am
+
+.PRECIOUS: Makefile
+
+
+@VALGRIND_CHECK_RULES@
+
+# Tell versions [3.59,3.63) of GNU make to not export all variables.
+# Otherwise a system limit (for SysV at least) may be exceeded.
+.NOEXPORT:
diff --git a/test/rtree/test_basic.cpp b/test/rtree/test_basic.cpp
new file mode 100644
index 0000000..4dd3354
--- /dev/null
+++ b/test/rtree/test_basic.cpp
@@ -0,0 +1,148 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_basic_search()
+{
+    stack_printer __stack_printer__("::rtree_test_basic_search");
+    using rt_type = rtree<int16_t, std::string>;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+    rt_type::extent_type expected_bb;
+
+    tree.insert({{0, 0}, {2, 2}}, "test");
+    expected_bb = {{0, 0}, {2, 2}};
+    assert(tree.extent() == expected_bb);
+    assert(tree.size() == 1);
+
+    tree.insert({{3, 3}, {5, 5}}, "test again");
+    expected_bb = {{0, 0}, {5, 5}};
+    assert(tree.extent() == expected_bb);
+    assert(tree.size() == 2);
+
+    tree.insert({{-2, 1}, {3, 6}}, "more test");
+    expected_bb = {{-2, 0}, {5, 6}};
+    assert(tree.extent() == expected_bb);
+    assert(tree.size() == 3);
+
+    tree.check_integrity(check_props);
+
+    // Verify the search method works.
+
+    rt_type::const_search_results res = ctree.search({1, 1}, search_type::overlap);
+
+    auto it = res.cbegin(), it_end = res.cend();
+
+    size_t n = std::distance(it, it_end);
+    assert(n == 2);
+
+    std::unordered_map<std::string, rt_type::extent_type> expected_values = {
+        {"test", {{0, 0}, {2, 2}}},
+        {"more test", {{-2, 1}, {3, 6}}},
+    };
+
+    for (; it != it_end; ++it)
+    {
+        cout << "bounding box: " << it.extent().to_string() << "; value: " << *it << "; depth: " << it.depth() << endl;
+        auto itv = expected_values.find(*it);
+        assert(itv != expected_values.end());
+        assert(itv->second == it.extent());
+        assert(it.depth() == 1);
+    }
+
+    // Perform an out-of-bound search by point.
+    std::vector<rt_type::point_type> pts = {
+        {-10, -10},
+        {1, 7},
+        {6, 3},
+    };
+
+    for (const rt_type::point_type& pt : pts)
+    {
+        res = ctree.search(pt, search_type::overlap);
+        assert(res.cbegin() == res.cend());
+    }
+}
+
+void rtree_test_basic_erase()
+{
+    stack_printer __stack_printer__("::rtree_test_basic_erase");
+    using rt_type = rtree<int16_t, std::string>;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+    tree.insert({{-2, -2}, {2, 2}}, "erase me");
+    assert(!tree.empty());
+    assert(tree.size() == 1);
+
+    rt_type::const_search_results res = ctree.search({0, 0}, search_type::overlap);
+
+    size_t n = std::distance(res.begin(), res.end());
+    assert(n == 1);
+
+    rt_type::const_iterator it = res.begin();
+    assert(it != res.end());
+
+    tree.erase(it);
+    assert(tree.empty());
+    assert(tree.size() == 0);
+    assert(rt_type::extent_type() == tree.extent());
+
+    tree.insert({{0, 0}, {2, 2}}, "erase me");
+    tree.insert({{-10, -4}, {0, 0}}, "erase me");
+    rt_type::extent_type expected_bb({-10, -4}, {2, 2});
+    assert(tree.extent() == expected_bb);
+    assert(tree.size() == 2);
+
+    res = ctree.search({-5, -2}, search_type::overlap);
+    n = std::distance(res.begin(), res.end());
+    assert(n == 1);
+    it = res.begin();
+    tree.erase(it);
+    assert(!tree.empty()); // there should be one value stored in the tree.
+    assert(tree.size() == 1);
+    expected_bb = {{0, 0}, {2, 2}};
+    assert(tree.extent() == expected_bb);
+
+    tree.check_integrity(check_props);
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_bulkload_main.cpp b/test/rtree/test_bulkload_main.cpp
new file mode 100644
index 0000000..8295c29
--- /dev/null
+++ b/test/rtree/test_bulkload_main.cpp
@@ -0,0 +1,281 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2018 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+#include <vector>
+#include <fstream>
+#include <unordered_map>
+
+using namespace mdds;
+using namespace std;
+
+void rtree_test_bl_empty()
+{
+    stack_printer __stack_printer__("::rtree_test_bl_empty");
+    using rt_type = rtree<int16_t, std::string>;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    // Load nothing.
+    rt_type::bulk_loader loader;
+    rt_type tree = loader.pack();
+    assert(tree.empty());
+    tree.check_integrity(check_props);
+}
+
+void rtree_test_bl_insert_points_move()
+{
+    stack_printer __stack_printer__("::rtree_test_bl_insert_points_move");
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d_forced_reinsertion>;
+    using key_type = rt_type::key_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    rt_type::bulk_loader loader;
+    for (key_type x = 0; x < 20; ++x)
+    {
+        key_type yn = (x == 0) ? 19 : 20;
+        for (key_type y = 0; y < yn; ++y)
+        {
+            std::ostringstream os;
+            os << '(' << x << ',' << y << ')';
+            loader.insert({x, y}, os.str());
+        }
+    }
+
+    auto tree = loader.pack();
+    assert(tree.size() == 399);
+    tree.check_integrity(check_props);
+    export_tree(tree, "rtree-test-bl-insert-points-move");
+}
+
+void rtree_test_bl_insert_points_copy()
+{
+    stack_printer __stack_printer__("::rtree_test_bl_insert_points_copy");
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d_forced_reinsertion>;
+    using point_type = rt_type::point_type;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    struct kv
+    {
+        point_type point;
+        std::string value;
+    };
+
+    std::vector<kv> values = {
+        {{0, 0}, "origin"},        {{125, 125}, "middle"},  {{22, 987}, "somewhere"},
+        {{-34, -200}, "negative"}, {{2, 3}, "near origin"},
+    };
+
+    // Insert less than max node size in order to test the packing
+    // implementation that doesn't involve per-level packing.
+    tiny_trait_2d_forced_reinsertion t;
+    assert(values.size() <= t.max_node_size);
+
+    for (size_t n_values = 1; n_values <= values.size(); ++n_values)
+    {
+        auto loader = rt_type::bulk_loader();
+
+        // Insert specified number of value(s).
+        for (size_t i = 0; i < n_values; ++i)
+            loader.insert(values[i].point, values[i].value);
+
+        // Populate and pack the tree.
+        auto tree = loader.pack();
+        tree.check_integrity(check_props);
+        assert(tree.size() == n_values);
+
+        // Make sure the inserted values are all there.
+        for (size_t i = 0; i < n_values; ++i)
+        {
+            auto res = tree.search(values[i].point, search_type::match);
+            assert(std::distance(res.begin(), res.end()) == 1);
+            auto it = res.begin();
+            assert(*it == values[i].value);
+
+            // The values should all be the immediate children of the root
+            // directory node.
+            assert(it.depth() == 1);
+        }
+    }
+}
+
+void rtree_test_bl_insert_extents_move()
+{
+    stack_printer __stack_printer__("::rtree_test_bl_insert_extents_move");
+    using rt_type = rtree<int16_t, only_movable, tiny_trait_2d_forced_reinsertion>;
+    using extent_type = rt_type::extent_type;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    struct kv
+    {
+        int16_t x;
+        int16_t y;
+        int16_t w;
+        int16_t h;
+        double value;
+    };
+
+    std::vector<kv> values = {
+        {2142, 2777, 1781, 1273, 1.0},   {5063, 2396, 765, 1019, 1.1},   {1887, 4935, 1400, 892, 1.2},
+        {4428, 4046, 1527, 1146, 1.3},   {2268, 6713, 1146, 2162, 1.4},  {7729, 7094, 2924, 1908, 1.5},
+        {10396, 2014, 6480, 892, 1.6},   {3158, 12302, 2035, 2289, 1.7}, {10777, 11032, 3432, 2289, 1.8},
+        {14334, 5063, 1781, 2797, 1.9},  {8365, 4301, 3051, 1019, 2.0},  {16619, 11794, 638, 511, 2.1},
+        {15222, 9254, 892, 511, 2.2},    {8111, 10142, 765, 638, 2.3},   {6587, 10397, 765, 511, 2.4},
+        {7475, 11793, 638, 1146, 2.5},   {8746, 11285, 765, 892, 2.6},   {16620, 3665, 511, 2162, 2.7},
+        {6332, 14714, 2162, 1908, 2.8},  {1634, 12048, 765, 5083, 2.9},  {15349, 16238, 1400, 1400, 3.0},
+        {11666, 14587, 1400, 1146, 3.1},
+    };
+
+    for (size_t n_values = 5; n_values <= values.size(); ++n_values)
+    {
+        rt_type::bulk_loader loader = rt_type::bulk_loader();
+
+        for (size_t i = 0; i < n_values; ++i)
+        {
+            const auto& v = values[i];
+            extent_type extent{{v.x, v.y}, {int16_t(v.x + v.w), int16_t(v.y + v.h)}};
+            only_movable vv(v.value);
+
+            loader.insert(extent, std::move(vv));
+        }
+
+        auto tree = loader.pack();
+        assert(tree.size() == n_values);
+        tree.check_integrity(check_props);
+
+        // Make sure the values are all there.
+        for (size_t i = 0; i < n_values; ++i)
+        {
+            const auto& v = values[i];
+            extent_type extent{{v.x, v.y}, {int16_t(v.x + v.w), int16_t(v.y + v.h)}};
+            auto res = tree.search(extent, search_type::match);
+            assert(std::distance(res.begin(), res.end()) == 1);
+            assert(res.begin()->get() == v.value);
+        }
+
+        if (n_values == values.size())
+            export_tree(tree, "rtree-test-bl-insert-extents-move");
+    }
+}
+
+void rtree_test_bl_insert_extents_copy()
+{
+    stack_printer __stack_printer__("::rtree_test_bl_insert_extents_copy");
+    using rt_type = rtree<int16_t, only_copyable, tiny_trait_2d_forced_reinsertion>;
+    using extent_type = rt_type::extent_type;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    struct kv
+    {
+        int16_t x;
+        int16_t y;
+        int16_t w;
+        int16_t h;
+        double value;
+    };
+
+    std::vector<kv> values = {
+        {2142, 2777, 1781, 1273, 1.0},   {5063, 2396, 765, 1019, 1.1},    {1887, 4935, 1400, 892, 1.2},
+        {4428, 4046, 1527, 1146, 1.3},   {2268, 6713, 1146, 2162, 1.4},   {7729, 7094, 2924, 1908, 1.5},
+        {10396, 2014, 6480, 892, 1.6},   {2904, 11286, 2035, 2289, 1.7},  {11412, 10524, 3432, 2289, 1.8},
+        {14334, 5063, 1781, 2797, 1.9},  {8365, 4301, 3051, 1019, 2.0},   {16619, 11794, 638, 511, 2.1},
+        {15222, 9254, 892, 511, 2.2},    {8111, 10142, 765, 638, 2.3},    {6587, 10397, 765, 511, 2.4},
+        {7475, 11793, 638, 1146, 2.5},   {8746, 11285, 765, 892, 2.6},    {16620, 3665, 511, 2162, 2.7},
+        {1760, 17762, 2162, 1908, 2.8},  {1634, 12048, 765, 5083, 2.9},   {15349, 16238, 1400, 1400, 3.0},
+        {11793, 13190, 1400, 1146, 3.1}, {4174, 6078, 1019, 638, 3.2},    {13191, 3412, 1781, 257, 3.3},
+        {6714, 11413, 511, 765, 3.4},    {2903, 14969, 892, 511, 3.5},    {3919, 16366, 638, 511, 3.6},
+        {4554, 15222, 892, 638, 3.7},    {2904, 16238, 511, 892, 3.8},    {1507, 20557, 6099, 257, 3.9},
+        {4047, 7221, 1273, 384, 4.0},    {12301, 3538, 638, 1908, 4.1},   {12174, 6460, 1146, 511, 4.2},
+        {13318, 4046, 1273, 384, 4.3},   {16620, 6459, 1019, 638, 4.4},   {14080, 8238, 511, 765, 4.5},
+        {8365, 12555, 765, 384, 4.6},    {16493, 7349, 511, 511, 4.7},    {7603, 11031, 511, 384, 4.8},
+        {13571, 13191, 638, 1527, 4.9},  {15858, 13826, 2035, 2035, 5.0}, {7094, 1380, 892, 3305, 5.1},
+        {7094, 6332, 1400, 1400, 5.2},   {10142, 8237, 2162, 384, 5.3},   {13444, 9761, 4, 130, 5.4},
+    };
+
+    for (size_t n_values = 22; n_values <= values.size(); ++n_values)
+    {
+        rt_type::bulk_loader loader = rt_type::bulk_loader();
+
+        for (size_t i = 0; i < n_values; ++i)
+        {
+            const auto& v = values[i];
+            extent_type extent{{v.x, v.y}, {int16_t(v.x + v.w), int16_t(v.y + v.h)}};
+            only_copyable vv(v.value);
+
+            loader.insert(extent, vv);
+        }
+
+        auto tree = loader.pack();
+        assert(tree.size() == n_values);
+        tree.check_integrity(check_props);
+
+        // Make sure the values are all there.
+        for (size_t i = 0; i < n_values; ++i)
+        {
+            const auto& v = values[i];
+            extent_type extent{{v.x, v.y}, {int16_t(v.x + v.w), int16_t(v.y + v.h)}};
+            auto res = tree.search(extent, search_type::match);
+            assert(std::distance(res.begin(), res.end()) == 1);
+            assert(res.begin()->get() == v.value);
+        }
+
+        if (n_values == values.size())
+            export_tree(tree, "rtree-test-bl-insert-extents-copy");
+    }
+}
+
+int main()
+{
+    try
+    {
+        rtree_test_bl_empty();
+        rtree_test_bl_insert_points_move();
+        rtree_test_bl_insert_points_copy();
+        rtree_test_bl_insert_extents_move();
+        rtree_test_bl_insert_extents_copy();
+    }
+    catch (const std::exception& e)
+    {
+        cout << "Test failed: " << e.what() << endl;
+        return EXIT_FAILURE;
+    }
+
+    cout << "Test finished successfully!" << endl;
+    return EXIT_SUCCESS;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_copy.cpp b/test/rtree/test_copy.cpp
new file mode 100644
index 0000000..dd4e5a9
--- /dev/null
+++ b/test/rtree/test_copy.cpp
@@ -0,0 +1,147 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_copy()
+{
+    stack_printer __stack_printer__("::rtree_test_copy");
+
+    using rt_type = rtree<double, double, tiny_trait_2d_forced_reinsertion>;
+    using point_type = rt_type::point_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    struct input
+    {
+        point_type start;
+        point_type end;
+        double value;
+    };
+
+    std::vector<input> inputs = {
+        {{0.0, 0.0}, {1.0, 1.0}, 1.0},    {{2.0, 2.0}, {2.1, 2.1}, 2.4},    {{100.0, 80.0}, {101.0, 85.0}, 100.0},
+        {{1.0, 75.0}, {2.0, 78.0}, 65.0}, {{1.0, 80.0}, {2.0, 82.0}, 68.0}, {{1.2, 1.0}, {2.2, 1.5}, 2.1},
+        {{2.2, 2.2}, {2.3, 2.4}, 3.5},    {{3.0, 3.0}, {3.3, 3.4}, 3.8},    {{4.0, 4.0}, {8.3, 12.4}, 13.8},
+        {{3.0, 5.0}, {4.3, 11.4}, 13.9},
+    };
+
+    rt_type tree;
+    for (const input& i : inputs)
+        tree.insert({i.start, i.end}, double(i.value));
+
+    auto copied(tree);
+
+    tree.check_integrity(check_props);
+    copied.check_integrity(check_props);
+
+    std::string str_src = tree.export_tree(rt_type::export_tree_type::formatted_node_properties);
+    std::string str_dst = tree.export_tree(rt_type::export_tree_type::formatted_node_properties);
+
+    assert(!str_src.empty() && str_src == str_dst);
+
+    // Test the "copy via assignment" scenario too.
+    auto copied_via_assign = tree;
+    copied_via_assign.check_integrity(check_props);
+    str_dst = copied_via_assign.export_tree(rt_type::export_tree_type::formatted_node_properties);
+
+    assert(!str_src.empty() && str_src == str_dst);
+}
+
+/**
+ * Make sure the rtree works with values that are only copyable (i.e. not
+ * movable).
+ */
+void rtree_test_only_copyable()
+{
+    stack_printer __stack_printer__("::rtree_test_only_copyable");
+
+    using rt_type = rtree<float, only_copyable, tiny_trait_2d_forced_reinsertion>;
+    using search_type = rt_type::search_type;
+    using extent_type = rt_type::extent_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+    only_copyable v(11.2);
+    tree.insert({{0, 0}, {2, 5}}, v);
+    v.set(12.5);
+    tree.insert({9, 9}, v);
+
+    tree.check_integrity(check_props);
+
+    {
+        // Immutable search.
+        auto cres = ctree.search({1, 1}, search_type::overlap);
+        assert(std::distance(cres.begin(), cres.end()) == 1);
+        assert(cres.begin()->get() == 11.2);
+
+        cres = ctree.search({9, 9}, search_type::overlap);
+        assert(std::distance(cres.cbegin(), cres.cend()) == 1);
+        assert(cres.cbegin()->get() == 12.5);
+    }
+
+    {
+        // Mutable search
+        auto res = tree.search({9, 9}, search_type::match);
+        assert(std::distance(res.begin(), res.end()) == 1);
+        assert(res.begin()->get() == 12.5);
+        auto it = res.begin();
+        (*it).set(34.5);
+
+        res = tree.search({9, 9}, search_type::match);
+        assert(std::distance(res.begin(), res.end()) == 1);
+        assert(res.begin()->get() == 34.5);
+    }
+
+    {
+        // Erase the only object via mutable iterator.
+        assert(tree.size() == 2);
+        rt_type::search_results res = tree.search({{0, 0}, {100, 100}}, search_type::overlap);
+        assert(std::distance(res.begin(), res.end()) == 2);
+
+        res = tree.search({9, 9}, search_type::match);
+        assert(std::distance(res.begin(), res.end()) == 1);
+        tree.erase(res.begin());
+
+        assert(tree.size() == 1);
+        res = tree.search({{0, 0}, {100, 100}}, search_type::overlap);
+        assert(std::distance(res.begin(), res.end()) == 1);
+        auto it = res.begin();
+        assert(it.extent() == extent_type({{0, 0}, {2, 5}}));
+        assert(it->get() == 11.2);
+    }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_directory_node_split.cpp b/test/rtree/test_directory_node_split.cpp
new file mode 100644
index 0000000..8f851a0
--- /dev/null
+++ b/test/rtree/test_directory_node_split.cpp
@@ -0,0 +1,85 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_directory_node_split()
+{
+    stack_printer __stack_printer__("::rtree_test_directory_node_split");
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d>;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+    using point = rt_type::point_type;
+    using bounding_box = rt_type::extent_type;
+
+    for (int16_t x = 0; x < 10; ++x)
+    {
+        for (int16_t y = 0; y < 10; ++y)
+        {
+            std::ostringstream os;
+            os << "(x=" << x << ",y=" << y << ")";
+            std::string v = os.str();
+            int16_t xe = x + 1, ye = y + 1;
+            point s({x, y}), e({xe, ye});
+            bounding_box bb(s, e);
+            cout << "Inserting value '" << v << "' to {" << bb.to_string() << "} ..." << endl;
+            tree.insert({s, e}, std::move(v));
+            tree.check_integrity(check_props);
+        }
+    }
+
+    assert(tree.size() == 100);
+
+    // All value nodes in this tree should be at depth 4 (root having the
+    // depth of 0).  Just check a few of them.
+
+    std::vector<point> pts = {
+        {5, 5},
+        {2, 3},
+        {7, 9},
+    };
+
+    for (const point& pt : pts)
+    {
+        auto res = ctree.search(pt, search_type::overlap);
+        auto it = res.cbegin();
+        assert(it != res.cend());
+        assert(it.depth() == 4);
+    }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_erase_directories.cpp b/test/rtree/test_erase_directories.cpp
new file mode 100644
index 0000000..c753a1e
--- /dev/null
+++ b/test/rtree/test_erase_directories.cpp
@@ -0,0 +1,100 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_erase_directories()
+{
+    stack_printer __stack_printer__("::rtree_test_erase_directories");
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d>;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+    using point = rt_type::point_type;
+    using bounding_box = rt_type::extent_type;
+
+    for (int16_t x = 0; x < 5; ++x)
+    {
+        for (int16_t y = 0; y < 5; ++y)
+        {
+            std::ostringstream os;
+            int16_t x2 = x * 2;
+            int16_t y2 = y * 2;
+            os << "(x=" << x2 << ",y=" << y2 << ")";
+            std::string v = os.str();
+            int16_t xe = x2 + 2, ye = y2 + 2;
+            point s({x2, y2}), e({xe, ye});
+            bounding_box bb(s, e);
+            tree.insert({s, e}, std::move(v));
+        }
+    }
+
+    assert(tree.size() == 25);
+    tree.check_integrity(check_props);
+    cout << tree.export_tree(rt_type::export_tree_type::formatted_node_properties) << endl;
+
+    size_t expected_size = 25;
+
+    for (int16_t x = 0; x < 5; ++x)
+    {
+        for (int16_t y = 0; y < 5; ++y)
+        {
+            int16_t x2 = x * 2 + 1;
+            int16_t y2 = y * 2 + 1;
+
+            cout << "erase at (" << x2 << ", " << y2 << ")" << endl;
+
+            auto res = ctree.search({x2, y2}, search_type::overlap);
+            auto it = res.begin(), ite = res.end();
+            size_t n = std::distance(it, ite);
+            assert(n == 1);
+
+            tree.erase(it);
+
+            assert(tree.size() == --expected_size);
+            tree.check_integrity(check_props);
+
+            res = ctree.search({x2, y2}, search_type::overlap);
+            n = std::distance(res.begin(), res.end());
+            assert(n == 0);
+        }
+    }
+
+    assert(tree.empty());
+    assert(tree.size() == 0);
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_exact_search_by_extent.cpp b/test/rtree/test_exact_search_by_extent.cpp
new file mode 100644
index 0000000..dfcde7c
--- /dev/null
+++ b/test/rtree/test_exact_search_by_extent.cpp
@@ -0,0 +1,85 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_exact_search_by_extent()
+{
+    stack_printer __stack_printer__("::rtree_test_exact_search_by_extent");
+
+    using rt_type = rtree<double, double, tiny_trait_2d_forced_reinsertion>;
+    using extent_type = rt_type::extent_type;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+    tree.insert({{0, 0}, {2, 2}}, 1.1);
+    tree.insert({{1, 1}, {3, 3}}, 1.2);
+    tree.insert({{2, 2}, {4, 4}}, 1.3);
+    tree.check_integrity(check_props);
+
+    {
+        // Immutable search
+        rt_type::const_search_results cres = ctree.search({{1, 1}, {3, 3}}, search_type::overlap);
+        size_t n = std::distance(cres.begin(), cres.end());
+        assert(n == 3);
+
+        cres = ctree.search({{1, 1}, {3, 3}}, search_type::match);
+        n = std::distance(cres.begin(), cres.end());
+        assert(n == 1);
+        auto it = cres.cbegin();
+        assert(*it == 1.2);
+        assert(it.extent() == extent_type({{1, 1}, {3, 3}}));
+        assert(it.depth() == 1);
+    }
+
+    {
+        // Mutable search
+        rt_type::search_results res = tree.search({{1, 1}, {3, 3}}, search_type::overlap);
+        size_t n = std::distance(res.begin(), res.end());
+        assert(n == 3);
+
+        // Modify the values.
+        for (double& v : res)
+            v += 1.0;
+
+        res = tree.search({{1, 1}, {3, 3}}, search_type::match);
+        n = std::distance(res.begin(), res.end());
+        assert(n == 1);
+        assert(*res.begin() == 2.2); // The value should be updated.
+    }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_exact_search_by_point.cpp b/test/rtree/test_exact_search_by_point.cpp
new file mode 100644
index 0000000..a40852c
--- /dev/null
+++ b/test/rtree/test_exact_search_by_point.cpp
@@ -0,0 +1,93 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_exact_search_by_point()
+{
+    stack_printer __stack_printer__("::rtree_test_exact_search_by_point");
+
+    using rt_type = rtree<double, double, tiny_trait_2d_forced_reinsertion>;
+    using point_type = rt_type::point_type;
+    using extent_type = rt_type::extent_type;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+    tree.insert({{0, 0}, {4, 4}}, 10.0);
+    tree.insert({1, 1}, 11.0);
+    tree.insert({3, 3}, 33.0);
+    tree.check_integrity(check_props);
+
+    rt_type::const_search_results res = ctree.search({1, 1}, search_type::overlap);
+    size_t n = std::distance(res.begin(), res.end());
+    assert(n == 2);
+
+    res = ctree.search({3, 3}, search_type::overlap);
+    n = std::distance(res.begin(), res.end());
+    assert(n == 2);
+
+    res = ctree.search({2, 2}, search_type::overlap);
+    n = std::distance(res.begin(), res.end());
+    assert(n == 1);
+    rt_type::const_iterator it = res.begin();
+    assert(*it == 10.0);
+    assert(it.extent() == extent_type({{0, 0}, {4, 4}}));
+
+    res = ctree.search({1, 1}, search_type::match);
+    n = std::distance(res.begin(), res.end());
+    assert(n == 1);
+    it = res.begin();
+    assert(*it == 11.0);
+    assert(it.extent().is_point());
+    assert(it.extent().start == point_type({1, 1}));
+
+    res = ctree.search({3, 3}, search_type::match);
+    n = std::distance(res.begin(), res.end());
+    assert(n == 1);
+    it = res.begin();
+    assert(*it == 33.0);
+    assert(it.extent().is_point());
+    assert(it.extent().start == point_type({3, 3}));
+
+    res = ctree.search({{0, 0}, {4, 4}}, search_type::match);
+    n = std::distance(res.begin(), res.end());
+    assert(n == 1);
+    it = res.begin();
+    assert(*it == 10.0);
+    assert(it.extent() == extent_type({{0, 0}, {4, 4}}));
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_forced_reinsertion.cpp b/test/rtree/test_forced_reinsertion.cpp
new file mode 100644
index 0000000..a23e29a
--- /dev/null
+++ b/test/rtree/test_forced_reinsertion.cpp
@@ -0,0 +1,82 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_forced_reinsertion()
+{
+    stack_printer __stack_printer__("::rtree_test_forced_reinsertion");
+
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d_forced_reinsertion>;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    rt_type tree;
+
+    for (int16_t i = 0; i < 6; ++i)
+    {
+        int16_t w = 1;
+        std::ostringstream os;
+        os << "foo" << i;
+        tree.insert({{i, i}, {int16_t(i + w), int16_t(i + w)}}, os.str());
+    }
+
+    assert(tree.size() == 6);
+    tree.check_integrity(check_props);
+
+    tree.clear();
+    assert(tree.empty());
+    assert(tree.size() == 0);
+    tree.check_integrity(check_props);
+
+    for (int16_t x = 0; x < 5; ++x)
+    {
+        for (int16_t y = 0; y < 5; ++y)
+        {
+            std::ostringstream os;
+            int16_t x2 = x * 2;
+            int16_t y2 = y * 2;
+            os << "(x=" << x2 << ",y=" << y2 << ")";
+            std::string v = os.str();
+            int16_t xe = x2 + 2, ye = y2 + 2;
+            tree.insert({{x2, y2}, {xe, ye}}, std::move(v));
+        }
+    }
+
+    tree.check_integrity(check_props);
+    assert(tree.size() == 25);
+
+    export_tree(tree, "rtree-test-forced-reinsertion");
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_geometry.cpp b/test/rtree/test_geometry.cpp
new file mode 100644
index 0000000..77b89b1
--- /dev/null
+++ b/test/rtree/test_geometry.cpp
@@ -0,0 +1,93 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_area_enlargement()
+{
+    stack_printer __stack_printer__("::rtree_test_area_enlargement");
+    using rt_type = rtree<int16_t, std::string>;
+    using bounding_box = rt_type::extent_type;
+    using mdds::detail::rtree::calc_area_enlargement;
+
+    struct check
+    {
+        bounding_box host;
+        bounding_box guest;
+        int16_t expected_area;
+    };
+
+    std::vector<check> checks = {
+        {{{0, 0}, {2, 2}}, {{2, 2}, {3, 3}}, 5}, // 3x3 - 2x2 = 5
+        {{{0, 0}, {2, 2}}, {{0, 1}, {1, 2}}, 0}, // no enlargement
+        {{{0, 0}, {3, 3}}, {{-3, 1}, {7, 2}}, 21}, // 10x3 - 3x3 = 21
+        {{{0, 0}, {0, 0}}, {{-1, -1}, {0, 0}}, 1}, // 1x1 = 1
+        {{{0, 0}, {1, 1}}, {{-4, -3}, {-3, -2}}, 19}, // 5x4 - 1x1 = 19
+    };
+
+    for (const check& c : checks)
+    {
+        int16_t area = calc_area_enlargement(c.host, c.guest);
+        assert(area == c.expected_area);
+    }
+}
+
+void rtree_test_center_point()
+{
+    stack_printer __stack_printer__("::rtree_test_center_point");
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d>;
+    using mdds::detail::rtree::get_center_point;
+    using extent_type = rt_type::extent_type;
+    using point_type = rt_type::point_type;
+
+    struct test_case
+    {
+        extent_type extent;
+        point_type expected;
+    };
+
+    std::vector<test_case> tcs = {
+        {{{0, 0}, {2, 2}}, {1, 1}},
+        {{{-2, -4}, {2, 4}}, {0, 0}},
+        {{{3, 5}, {8, 10}}, {5, 7}},
+    };
+
+    for (const test_case& tc : tcs)
+    {
+        cout << "extent: " << tc.extent.to_string() << endl;
+        auto pt = get_center_point(tc.extent);
+        assert(pt == tc.expected);
+    }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_global_rtree.hpp b/test/rtree/test_global_rtree.hpp
new file mode 100644
index 0000000..7819cda
--- /dev/null
+++ b/test/rtree/test_global_rtree.hpp
@@ -0,0 +1,148 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2018 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#ifndef INCLUDED_MDDS_TEST_GLOBAL_RTREE_HPP
+#define INCLUDED_MDDS_TEST_GLOBAL_RTREE_HPP
+
+#define MDDS_RTREE_DEBUG 1
+#include <mdds/rtree.hpp>
+#include <fstream>
+
+struct tiny_trait_1d
+{
+    constexpr static size_t dimensions = 1;
+    constexpr static size_t min_node_size = 2;
+    constexpr static size_t max_node_size = 5;
+    constexpr static size_t max_tree_depth = 100;
+
+    constexpr static bool enable_forced_reinsertion = false;
+    constexpr static size_t reinsertion_size = 2;
+};
+
+struct tiny_trait_2d
+{
+    constexpr static size_t dimensions = 2;
+    constexpr static size_t min_node_size = 2;
+    constexpr static size_t max_node_size = 5;
+    constexpr static size_t max_tree_depth = 100;
+
+    constexpr static bool enable_forced_reinsertion = false;
+    constexpr static size_t reinsertion_size = 2;
+};
+
+struct tiny_trait_2d_forced_reinsertion
+{
+    constexpr static size_t dimensions = 2;
+    constexpr static size_t min_node_size = 2;
+    constexpr static size_t max_node_size = 5;
+    constexpr static size_t max_tree_depth = 100;
+
+    constexpr static bool enable_forced_reinsertion = true;
+    constexpr static size_t reinsertion_size = 2;
+};
+
+class only_movable
+{
+    double m_value;
+
+public:
+    only_movable() : m_value(0.0)
+    {}
+    only_movable(double v) : m_value(v)
+    {}
+    only_movable(const only_movable&) = delete;
+    only_movable(only_movable&& other) : m_value(other.m_value)
+    {
+        other.m_value = 0.0;
+    }
+
+    double get() const
+    {
+        return m_value;
+    }
+};
+
+class only_copyable
+{
+    double m_value;
+
+public:
+    only_copyable() : m_value(0.0)
+    {}
+    only_copyable(double v) : m_value(v)
+    {}
+    only_copyable(const only_copyable& other) : m_value(other.m_value)
+    {}
+
+    only_copyable(only_copyable&&) = delete;
+
+    void set(double v)
+    {
+        m_value = v;
+    }
+    double get() const
+    {
+        return m_value;
+    }
+};
+
+template<typename T>
+void export_tree(const T& tree, const std::string& basename)
+{
+    {
+        std::ofstream fout(basename + ".obj");
+        fout << tree.export_tree(T::export_tree_type::extent_as_obj);
+    }
+
+    {
+        std::ofstream fout(basename + ".svg");
+        fout << tree.export_tree(T::export_tree_type::extent_as_svg);
+    }
+}
+
+void rtree_test_intersection();
+void rtree_test_square_distance();
+void rtree_test_center_point();
+void rtree_test_area_enlargement();
+void rtree_test_basic_search();
+void rtree_test_basic_erase();
+void rtree_test_node_split();
+void rtree_test_directory_node_split();
+void rtree_test_erase_directories();
+void rtree_test_forced_reinsertion();
+void rtree_test_move();
+void rtree_test_move_custom_type();
+void rtree_test_copy();
+void rtree_test_point_objects();
+void rtree_test_only_copyable();
+void rtree_test_exact_search_by_extent();
+void rtree_test_exact_search_by_point();
+
+#endif
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_intersection.cpp b/test/rtree/test_intersection.cpp
new file mode 100644
index 0000000..0cf5b93
--- /dev/null
+++ b/test/rtree/test_intersection.cpp
@@ -0,0 +1,83 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_intersection()
+{
+    stack_printer __stack_printer__("::rtree_test_intersection");
+    using rt_type = rtree<int16_t, std::string>;
+    using bounding_box = rt_type::extent_type;
+    using mdds::detail::rtree::calc_intersection;
+    using mdds::detail::rtree::calc_linear_intersection;
+
+    struct check
+    {
+        bounding_box bb1;
+        bounding_box bb2;
+        int16_t expected_length1;
+        int16_t expected_length2;
+    };
+
+    std::vector<check> checks = {
+        // bounding box 1           bounding box 2
+        {{{0, 0}, {3, 6}}, {{1, 2}, {7, 5}}, 2, 3},       {{{3, 2}, {7, 10}}, {{1, 10}, {10, 11}}, 4, 0},
+        {{{3, 2}, {7, 10}}, {{1, 9}, {10, 11}}, 4, 1},    {{{3, 2}, {7, 6}}, {{5, 4}, {11, 8}}, 2, 2},
+        {{{-2, -8}, {2, -5}}, {{0, -10}, {8, -1}}, 2, 3}, {{{2, 2}, {20, 12}}, {{5, 6}, {16, 9}}, 11, 3},
+        {{{0, 0}, {6, 6}}, {{0, 0}, {2, 3}}, 2, 3},
+    };
+
+    for (const check& c : checks)
+    {
+        int16_t length1 = calc_linear_intersection<bounding_box>(0, c.bb1, c.bb2);
+        assert(length1 == c.expected_length1);
+        int16_t length2 = calc_linear_intersection<bounding_box>(1, c.bb1, c.bb2);
+        assert(length2 == c.expected_length2);
+
+        int16_t area = calc_intersection<bounding_box>(c.bb1, c.bb2);
+        int16_t expected_area = c.expected_length1 * c.expected_length2;
+        assert(area == expected_area);
+
+        // Swap the boxes and run the same tests. We should get the same results.
+
+        length1 = calc_linear_intersection<bounding_box>(0, c.bb2, c.bb1);
+        assert(length1 == c.expected_length1);
+        length2 = calc_linear_intersection<bounding_box>(1, c.bb2, c.bb1);
+        assert(length2 == c.expected_length2);
+
+        area = calc_intersection<bounding_box>(c.bb2, c.bb1);
+        assert(area == expected_area);
+    }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_main.cpp b/test/rtree/test_main.cpp
new file mode 100644
index 0000000..6e776a8
--- /dev/null
+++ b/test/rtree/test_main.cpp
@@ -0,0 +1,67 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2018 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using namespace std;
+
+int main()
+{
+    try
+    {
+        rtree_test_intersection();
+        rtree_test_square_distance();
+        rtree_test_center_point();
+        rtree_test_area_enlargement();
+        rtree_test_basic_search();
+        rtree_test_basic_erase();
+        rtree_test_node_split();
+        rtree_test_directory_node_split();
+        rtree_test_erase_directories();
+        rtree_test_forced_reinsertion();
+        rtree_test_move();
+        rtree_test_move_custom_type();
+        rtree_test_copy();
+        rtree_test_point_objects();
+        rtree_test_only_copyable();
+        rtree_test_exact_search_by_extent();
+        rtree_test_exact_search_by_point();
+    }
+    catch (const std::exception& e)
+    {
+        cout << "Test failed: " << e.what() << endl;
+        return EXIT_FAILURE;
+    }
+
+    cout << "Test finished successfully!" << endl;
+
+    return EXIT_SUCCESS;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_move.cpp b/test/rtree/test_move.cpp
new file mode 100644
index 0000000..1a81b82
--- /dev/null
+++ b/test/rtree/test_move.cpp
@@ -0,0 +1,134 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_move()
+{
+    stack_printer __stack_printer__("::rtree_test_move");
+
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d_forced_reinsertion>;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    rt_type tree;
+
+    for (int16_t x = 0; x < 5; ++x)
+    {
+        for (int16_t y = 0; y < 5; ++y)
+        {
+            std::ostringstream os;
+            int16_t x2 = x * 2;
+            int16_t y2 = y * 2;
+            os << "(x=" << x2 << ",y=" << y2 << ")";
+            std::string v = os.str();
+            int16_t xe = x2 + 2, ye = y2 + 2;
+            tree.insert({{x2, y2}, {xe, ye}}, std::move(v));
+        }
+    }
+
+    tree.check_integrity(check_props);
+    assert(tree.size() == 25);
+
+    // moved via constructor.
+    rt_type tree_moved(std::move(tree));
+    tree.check_integrity(check_props);
+    tree_moved.check_integrity(check_props);
+    assert(tree.empty());
+    assert(tree.size() == 0);
+    assert(tree_moved.size() == 25);
+
+    // moved via assignment operator.
+    rt_type tree_moved_2;
+    tree_moved_2.check_integrity(check_props);
+    tree_moved_2 = std::move(tree_moved);
+    tree_moved.check_integrity(check_props);
+    tree_moved_2.check_integrity(check_props);
+    assert(tree_moved.empty());
+    assert(tree_moved.size() == 0);
+    assert(tree_moved_2.size() == 25);
+}
+
+/**
+ * Make sure we can 1) store objects that are only movable but not copyable,
+ * and 2) the whole tree can still be moved.
+ */
+void rtree_test_move_custom_type()
+{
+    stack_printer __stack_printer__("::rtree_test_move_custom_type");
+
+    using rt_type = rtree<double, only_movable, tiny_trait_2d_forced_reinsertion>;
+    using point_type = rt_type::point_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    {
+        // Make sure you can actually move an object of this type.
+        only_movable v1(1.5);
+        only_movable v2(std::move(v1));
+    }
+
+    struct input
+    {
+        point_type start;
+        point_type end;
+        double value;
+    };
+
+    std::vector<input> inputs = {
+        {{0.0, 0.0}, {1.0, 1.0}, 1.0},    {{2.0, 2.0}, {2.1, 2.1}, 2.4},    {{100.0, 80.0}, {101.0, 85.0}, 100.0},
+        {{1.0, 75.0}, {2.0, 78.0}, 65.0}, {{1.0, 80.0}, {2.0, 82.0}, 68.0}, {{1.2, 1.0}, {2.2, 1.5}, 2.1},
+        {{2.2, 2.2}, {2.3, 2.4}, 3.5},    {{3.0, 3.0}, {3.3, 3.4}, 3.8},    {{4.0, 4.0}, {8.3, 12.4}, 13.8},
+        {{3.0, 5.0}, {4.3, 11.4}, 13.9},
+    };
+
+    rt_type tree;
+
+    for (const input& i : inputs)
+        tree.insert({i.start, i.end}, only_movable(i.value));
+
+    assert(tree.size() == inputs.size());
+
+    tree.check_integrity(check_props);
+
+    export_tree(tree, "rtree-test-move-custom-type");
+
+    // Now move the tree.
+    rt_type tree_moved = std::move(tree);
+    tree.check_integrity(check_props);
+    tree_moved.check_integrity(check_props);
+    assert(tree.empty());
+    assert(tree_moved.size() == inputs.size());
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_node_split.cpp b/test/rtree/test_node_split.cpp
new file mode 100644
index 0000000..c09727a
--- /dev/null
+++ b/test/rtree/test_node_split.cpp
@@ -0,0 +1,140 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_node_split()
+{
+    stack_printer __stack_printer__("::rtree_test_node_split");
+    using rt_type = rtree<int16_t, std::string, tiny_trait_2d>;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = true;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+
+    // Inserting 6 entries should cause the root directory node to split.
+    // After the split, the root node should become a non-leaf directory
+    // storing two leaf directory nodes as its children.
+
+    for (int16_t i = 0; i < 6; ++i)
+    {
+        int16_t w = 1;
+        std::ostringstream os;
+        os << "foo" << i;
+        tree.insert({{i, i}, {int16_t(i + w), int16_t(i + w)}}, os.str());
+    }
+
+    assert(tree.size() == 6);
+
+    cout << tree.export_tree(rt_type::export_tree_type::formatted_node_properties) << endl;
+
+    size_t count_values = 0;
+    size_t count_leaf = 0;
+    size_t count_nonleaf = 0;
+
+    auto walker = [&](const rt_type::node_properties& np) {
+        switch (np.type)
+        {
+            case rt_type::node_type::value:
+                ++count_values;
+                break;
+            case rt_type::node_type::directory_leaf:
+                ++count_leaf;
+                break;
+            case rt_type::node_type::directory_nonleaf:
+                ++count_nonleaf;
+                break;
+            default:;
+        }
+    };
+
+    tree.walk(walker);
+
+    assert(count_values == 6);
+    assert(count_leaf == 2);
+    assert(count_nonleaf == 1);
+
+    tree.check_integrity(check_props);
+
+    // Adding two more entries will cause one of the leaf directory nodes
+    // below the root node to split.
+
+    for (int16_t i = 6; i < 8; ++i)
+    {
+        int16_t w = 1;
+        std::ostringstream os;
+        os << "bar" << i;
+        tree.insert({{i, i}, {int16_t(i + w), int16_t(i + w)}}, os.str());
+    }
+
+    assert(tree.size() == 8);
+    tree.check_integrity(check_props);
+
+    // Count all the nodes again.
+    count_values = 0;
+    count_leaf = 0;
+    count_nonleaf = 0;
+
+    tree.walk(walker);
+
+    assert(count_values == 8);
+    assert(count_leaf == 3);
+    assert(count_nonleaf == 1);
+
+    // Erase the entry at (0, 0).  There should be only one match.  Erasing
+    // this entry will cause the node to be underfilled.
+
+    rt_type::const_search_results res = ctree.search({0, 0}, search_type::overlap);
+    auto it = res.cbegin();
+    assert(it != res.cend());
+    assert(std::distance(it, res.cend()) == 1);
+    tree.erase(it);
+
+    assert(tree.size() == 7);
+    tree.check_integrity(check_props);
+
+    // Count all the nodes again.
+    count_values = 0;
+    count_leaf = 0;
+    count_nonleaf = 0;
+
+    tree.walk(walker);
+
+    assert(count_values == 7);
+    assert(count_leaf == 2);
+    assert(count_nonleaf == 1);
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_point_objects.cpp b/test/rtree/test_point_objects.cpp
new file mode 100644
index 0000000..b2a3602
--- /dev/null
+++ b/test/rtree/test_point_objects.cpp
@@ -0,0 +1,79 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_point_objects()
+{
+    stack_printer __stack_printer__("::rtree_test_point_objects");
+
+    using rt_type = rtree<double, double, tiny_trait_2d_forced_reinsertion>;
+    using key_type = rt_type::key_type;
+    using search_type = rt_type::search_type;
+    rt_type::integrity_check_properties check_props;
+    check_props.throw_on_first_error = false;
+
+    rt_type tree;
+    const rt_type& ctree = tree;
+
+    for (key_type x = 0; x < 10; ++x)
+    {
+        for (key_type y = 0; y < 10; ++y)
+        {
+            tree.insert({x, y}, x * y);
+        }
+    }
+
+    tree.check_integrity(check_props);
+
+    for (key_type x = 0; x < 10; ++x)
+    {
+        for (key_type y = 0; y < 10; ++y)
+        {
+            auto results = tree.search({x, y}, search_type::overlap);
+            assert(std::distance(results.begin(), results.end()) == 1);
+            double expected = x * y;
+            auto it = results.begin();
+            assert(expected == *it);
+        }
+    }
+
+    // Test an extent-based search on point data.
+    auto results = ctree.search({{0, 0}, {3, 3}}, search_type::overlap);
+    size_t n_results = std::distance(results.cbegin(), results.cend());
+    assert(n_results == 16);
+
+    export_tree(tree, "rtree-test-point-objects");
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/test/rtree/test_square_distance.cpp b/test/rtree/test_square_distance.cpp
new file mode 100644
index 0000000..4ea80d3
--- /dev/null
+++ b/test/rtree/test_square_distance.cpp
@@ -0,0 +1,105 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2021 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#include "test_global.hpp" // This must be the first header to be included.
+#include "test_global_rtree.hpp"
+
+using mdds::rtree;
+using std::cout;
+using std::endl;
+
+void rtree_test_square_distance()
+{
+    stack_printer __stack_printer__("::rtree_test_square_distance");
+    using mdds::detail::rtree::calc_square_distance;
+
+    {
+        // 1 dimensional unsigned
+        using rt_type = rtree<uint16_t, std::string, tiny_trait_1d>;
+        using point_type = rt_type::point_type;
+
+        struct test_case
+        {
+            point_type p1;
+            point_type p2;
+            uint16_t expected;
+        };
+
+        std::vector<test_case> tcs = {
+            {{3}, {5}, 4},
+            {{9}, {2}, 49},
+            {{0}, {0}, 0},
+        };
+
+        for (const test_case& tc : tcs)
+        {
+            cout << "p1: " << tc.p1.to_string() << "; p2: " << tc.p2.to_string() << endl;
+
+            uint16_t dist = calc_square_distance<point_type>(tc.p1, tc.p2);
+            assert(dist == tc.expected);
+
+            // Flip the value to make sure we still get the same result.
+            dist = calc_square_distance<point_type>(tc.p2, tc.p1);
+            assert(dist == tc.expected);
+        }
+    }
+
+    {
+        // 2 dimensional unsigned
+        using rt_type = rtree<uint16_t, std::string, tiny_trait_2d>;
+        using point_type = rt_type::point_type;
+
+        struct test_case
+        {
+            point_type p1;
+            point_type p2;
+            uint16_t expected;
+        };
+
+        std::vector<test_case> tcs = {
+            {{0, 0}, {0, 0}, 0},
+            {{0, 0}, {1, 1}, 2},
+            {{0, 0}, {2, 2}, 8},
+            {{3, 0}, {0, 4}, 25},
+        };
+
+        for (const test_case& tc : tcs)
+        {
+            cout << "p1: " << tc.p1.to_string() << "; p2: " << tc.p2.to_string() << endl;
+
+            uint16_t dist = calc_square_distance<point_type>(tc.p1, tc.p2);
+            assert(dist == tc.expected);
+
+            // Flip the value to make sure we still get the same result.
+            dist = calc_square_distance<point_type>(tc.p2, tc.p1);
+            assert(dist == tc.expected);
+        }
+    }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */