summaryrefslogtreecommitdiffstats
path: root/test/flat_segment_tree
diff options
context:
space:
mode:
Diffstat (limited to 'test/flat_segment_tree')
-rw-r--r--test/flat_segment_tree/Makefile.am14
-rw-r--r--test/flat_segment_tree/Makefile.in990
-rw-r--r--test/flat_segment_tree/test_main.cpp2590
3 files changed, 3594 insertions, 0 deletions
diff --git a/test/flat_segment_tree/Makefile.am b/test/flat_segment_tree/Makefile.am
new file mode 100644
index 0000000..b4927a7
--- /dev/null
+++ b/test/flat_segment_tree/Makefile.am
@@ -0,0 +1,14 @@
+AM_CPPFLAGS = \
+ -I$(top_srcdir)/include \
+ -I$(top_srcdir)/test/include \
+ $(CXXFLAGS_UNITTESTS)
+
+check_PROGRAMS = test-main
+
+test_main_SOURCES = \
+ test_main.cpp \
+ $(top_srcdir)/test/test_global.cpp
+
+TESTS = test-main
+
+@VALGRIND_CHECK_RULES@
diff --git a/test/flat_segment_tree/Makefile.in b/test/flat_segment_tree/Makefile.in
new file mode 100644
index 0000000..23eb042
--- /dev/null
+++ b/test/flat_segment_tree/Makefile.in
@@ -0,0 +1,990 @@
+# 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)
+TESTS = test-main$(EXEEXT)
+subdir = test/flat_segment_tree
+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_main_OBJECTS = test_main.$(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_main.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_main_SOURCES)
+DIST_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)
+
+test_main_SOURCES = \
+ test_main.cpp \
+ $(top_srcdir)/test/test_global.cpp
+
+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/flat_segment_tree/Makefile'; \
+ $(am__cd) $(top_srcdir) && \
+ $(AUTOMAKE) --foreign test/flat_segment_tree/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-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_main.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.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 "$(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_main.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_main.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/flat_segment_tree/test_main.cpp b/test/flat_segment_tree/test_main.cpp
new file mode 100644
index 0000000..c0f5f66
--- /dev/null
+++ b/test/flat_segment_tree/test_main.cpp
@@ -0,0 +1,2590 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2008-2023 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 "mdds/flat_segment_tree.hpp"
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <limits>
+#include <iterator>
+#include <algorithm>
+#include <memory>
+
+using namespace mdds;
+
+void print_title(const char* msg)
+{
+ cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
+ cout << " " << msg << endl;
+ cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
+}
+
+void fst_test_leaf_search()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ {
+ print_title("Simple insert test");
+ flat_segment_tree<int, int> int_ranges(0, 100, -1);
+ for (int i = 0; i < 20; ++i)
+ {
+ int start = i * 5;
+ int end = start + 5;
+ int_ranges.insert_front(start, end, i);
+ }
+ int_ranges.dump_leaf_nodes();
+ }
+
+ {
+ print_title("Merge test 1");
+ flat_segment_tree<int, int> merge_test(0, 100, -1);
+ merge_test.insert_front(10, 20, 5);
+ merge_test.dump_leaf_nodes();
+ merge_test.insert_front(15, 30, 5);
+ merge_test.dump_leaf_nodes();
+ merge_test.insert_front(30, 50, 5);
+ merge_test.dump_leaf_nodes();
+ merge_test.insert_front(8, 11, 5);
+ merge_test.dump_leaf_nodes();
+ merge_test.insert_front(5, 8, 5);
+ merge_test.dump_leaf_nodes();
+ }
+
+ {
+ print_title("Merge test 2");
+ flat_segment_tree<int, int> merge_test(0, 100, -1);
+
+ // This should not change the node configuration.
+ merge_test.insert_front(10, 90, -1);
+ merge_test.dump_leaf_nodes();
+
+ for (int i = 10; i <= 80; i += 10)
+ merge_test.insert_front(i, i + 10, i);
+ merge_test.dump_leaf_nodes();
+ merge_test.insert_front(10, 90, -1);
+ merge_test.dump_leaf_nodes();
+
+ for (int i = 10; i <= 80; i += 10)
+ merge_test.insert_front(i, i + 10, i);
+ merge_test.dump_leaf_nodes();
+ merge_test.insert_front(8, 92, -1);
+ merge_test.dump_leaf_nodes();
+
+ for (int i = 10; i <= 80; i += 10)
+ merge_test.insert_front(i, i + 10, i);
+ merge_test.dump_leaf_nodes();
+ merge_test.insert_front(12, 88, 25);
+ merge_test.dump_leaf_nodes();
+ }
+
+ {
+ print_title("Search test");
+ flat_segment_tree<int, int> db(0, 100, -1);
+ for (int i = 0; i < 10; ++i)
+ {
+ int key = i * 10;
+ int val = i * 5;
+ db.insert_front(key, key + 10, val);
+ }
+ db.dump_leaf_nodes();
+ for (int i = 0; i <= 100; ++i)
+ {
+ int val = 0;
+ if (db.search(i, val).second)
+ cout << "key = " << i << "; value = " << val << endl;
+ else
+ cout << "key = " << i << "; (value not found)" << endl;
+ }
+ for (int i = 0; i <= 100; ++i)
+ {
+ int val = 0, start, end;
+ if (db.search(i, val, &start, &end).second)
+ cout << "key = " << i << "; value = " << val << "(span: " << start << " - " << end << ")" << endl;
+ else
+ cout << "key = " << i << "; (value not found)" << endl;
+ }
+ }
+}
+
+void fst_test_leaf_search_2()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ using db_type = mdds::flat_segment_tree<int32_t, std::string>;
+ db_type db(0, 8, "-");
+ db.insert_back(2, 4, "2-4");
+ db.insert_back(4, 6, "4-6");
+
+ db_type::const_iterator it = db.search(-1); // out-of-bound
+ assert(it == db.end());
+
+ it = db.search(8); // out-of-bound
+ assert(it == db.end());
+
+ struct check
+ {
+ int32_t key;
+ int32_t start;
+ int32_t end;
+ std::string value;
+ };
+
+ std::vector<check> checks = {
+ {0, 0, 2, "-"}, {1, 0, 2, "-"}, {2, 2, 4, "2-4"}, {3, 2, 4, "2-4"},
+ {4, 4, 6, "4-6"}, {5, 4, 6, "4-6"}, {6, 6, 8, "-"}, {7, 6, 8, "-"},
+ };
+
+ // variant of search() without a position hint
+ for (const auto& c : checks)
+ {
+ it = db.search(c.key);
+ assert(it != db.end());
+ assert(it->first == c.start);
+ assert(it->second == c.value);
+
+ auto sit = it.to_segment();
+ assert(sit->start == c.start);
+ assert(sit->end == c.end);
+ assert(sit->value == c.value);
+ }
+
+ // variant of search() with a position hint
+
+ it = db.search(db.begin(), -1); // out-of-bound
+ assert(it == db.end());
+
+ it = db.search(db.begin(), 8); // out-of-bound
+ assert(it == db.end());
+
+ it = db.begin();
+ for (const auto& c : checks)
+ {
+ it = db.search(it, c.key);
+ assert(it != db.end());
+ assert(it->first == c.start);
+ assert(it->second == c.value);
+
+ auto sit = it.to_segment();
+ assert(sit->start == c.start);
+ assert(sit->end == c.end);
+ assert(sit->value == c.value);
+ }
+}
+
+/**
+ * Test tree construction of flat_segment_tree.
+ */
+void fst_test_tree_build()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ {
+ int lower = 0, upper = 100, delta = 10;
+ flat_segment_tree<int, int> db(lower, upper, 0);
+ {
+ stack_printer __stack_printer2__("::fst_test_tree_build insertion");
+ for (int i = lower; i < upper; i += delta)
+ db.insert_front(i, i + delta, i * 2);
+ }
+ db.dump_leaf_nodes();
+
+ {
+ stack_printer __stack_printer2__("::fst_test_tree_build tree construction");
+ db.build_tree();
+ db.dump_tree();
+ }
+ }
+
+ {
+ flat_segment_tree<int, int> db(0, 10, 0);
+ db.dump_leaf_nodes();
+ }
+}
+
+void fst_perf_test_search_leaf()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ int lower = 0, upper = 50000;
+ flat_segment_tree<int, int> db(lower, upper, 0);
+ for (int i = upper - 1; i >= lower; --i)
+ db.insert_front(i, i + 1, i);
+
+ int success = 0, failure = 0;
+ int val;
+ for (int i = lower; i < upper; ++i)
+ {
+ if (db.search(i, val).second)
+ ++success;
+ else
+ ++failure;
+ }
+ fprintf(stdout, "fst_perf_test_search_leaf: success (%d) failure (%d)\n", success, failure);
+}
+
+void fst_perf_test_search_tree()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ int lower = 0, upper = 5000000;
+ flat_segment_tree<int, int> db(lower, upper, 0);
+ for (int i = upper - 1; i >= lower; --i)
+ db.insert_front(i, i + 1, i);
+
+ {
+ stack_printer sp2("::fst_perf_test_search_tree (build tree)");
+ db.build_tree();
+ }
+
+ int success = 0, failure = 0;
+ {
+ stack_printer sp2("::fst_perf_test_search_tree (search tree)");
+ int val;
+ for (int i = lower; i < upper; ++i)
+ {
+ if (db.search_tree(i, val).second)
+ ++success;
+ else
+ ++failure;
+ }
+ }
+
+ fprintf(stdout, "fst_perf_test_search: success (%d) failure (%d)\n", success, failure);
+}
+
+void fst_test_tree_search()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<int, int> fst_type;
+ int lower = 0, upper = 200, delta = 5;
+ fst_type db(lower, upper, 0);
+ for (int i = lower; i < upper; i += delta)
+ db.insert_front(i, i + delta, i);
+
+ db.build_tree();
+ db.dump_tree();
+ db.dump_leaf_nodes();
+
+ int val, start, end;
+ int success = 0, failure = 0;
+ for (int i = lower - 10; i < upper + 10; ++i)
+ {
+ if (db.search_tree(i, val, &start, &end).second)
+ {
+ cout << "key = " << i << "; value = " << val << " (" << start << "-" << end << ")" << endl;
+ ++success;
+ }
+ else
+ {
+ ++failure;
+ cout << "key = " << i << " (search failed)" << endl;
+ }
+ }
+ cout << "search: success (" << success << ") failure (" << failure << ")" << endl;
+
+ // Make sure search_tree() returns correct iterator position.
+ db.clear();
+ db.insert_back(5, 10, 2);
+ db.insert_back(15, 18, 3);
+ db.insert_back(23, 28, 4);
+ db.build_tree();
+
+ typedef std::pair<fst_type::const_iterator, bool> ret_type;
+ ret_type ret = db.search_tree(0, val, &start, &end);
+ assert(ret.second);
+ assert(start == 0 && end == 5 && val == 0);
+ assert(ret.first == db.begin());
+
+ ret = db.search_tree(6, val, &start, &end);
+ assert(ret.second);
+ assert(start == 5 && end == 10 && val == 2);
+ fst_type::const_iterator check = db.begin();
+ ++check; // 5-10 is the 2nd segment from the top.
+ assert(ret.first == check);
+
+ ret = db.search_tree(17, val, &start, &end);
+ assert(ret.second);
+ assert(start == 15 && end == 18 && val == 3);
+ std::advance(check, 2);
+ assert(ret.first == check);
+
+ ret = db.search_tree(55, val, &start, &end);
+ assert(ret.second);
+ assert(start == 28 && end == upper && val == 0);
+ std::advance(check, 3);
+ assert(ret.first == check);
+
+ ret = db.search_tree(upper + 10, val, &start, &end);
+ assert(!ret.second); // This search should fail.
+ assert(ret.first == db.end());
+}
+
+void fst_test_tree_search_2()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ using db_type = mdds::flat_segment_tree<int32_t, std::string>;
+ db_type db(0, 8, "-");
+ db.insert_back(2, 4, "2-4");
+ db.insert_back(4, 6, "4-6");
+
+ db.build_tree();
+
+ db_type::const_iterator it = db.search_tree(-1); // out-of-bound
+ assert(it == db.end());
+
+ it = db.search_tree(8); // out-of-bound
+ assert(it == db.end());
+
+ struct check
+ {
+ int32_t key;
+ int32_t start;
+ int32_t end;
+ std::string value;
+ };
+
+ std::vector<check> checks = {
+ {0, 0, 2, "-"}, {1, 0, 2, "-"}, {2, 2, 4, "2-4"}, {3, 2, 4, "2-4"},
+ {4, 4, 6, "4-6"}, {5, 4, 6, "4-6"}, {6, 6, 8, "-"}, {7, 6, 8, "-"},
+ };
+
+ // variant of search() without a position hint
+ for (const auto& c : checks)
+ {
+ it = db.search_tree(c.key);
+ assert(it != db.end());
+ assert(it->first == c.start);
+ assert(it->second == c.value);
+
+ auto sit = it.to_segment();
+ assert(sit->start == c.start);
+ assert(sit->end == c.end);
+ assert(sit->value == c.value);
+ }
+}
+
+void test_single_tree_search(const flat_segment_tree<int, int>& db, int key, int val, int start, int end)
+{
+ int r_val, r_start, r_end;
+ if (db.search_tree(key, r_val, &r_start, &r_end).second)
+ assert(r_val == val && r_start == start && r_end == end);
+ else
+ assert(!"tree search failed!");
+}
+
+template<typename key_type, typename value_type>
+void build_and_dump(flat_segment_tree<key_type, value_type>& db)
+{
+ db.build_tree();
+ db.dump_tree();
+ db.dump_leaf_nodes();
+}
+
+template<typename key_type, typename value_type>
+bool check_leaf_nodes(
+ const flat_segment_tree<key_type, value_type>& db, const key_type* keys, const value_type* values, size_t key_size)
+{
+ if (key_size <= 1)
+ return false;
+
+ std::vector<key_type> key_checks;
+ key_checks.reserve(key_size);
+ for (size_t i = 0; i < key_size; ++i)
+ key_checks.push_back(keys[i]);
+
+ if (!db.verify_keys(key_checks))
+ return false;
+
+ std::vector<value_type> value_checks;
+ value_checks.reserve(key_size - 1);
+ for (size_t i = 0; i < key_size - 1; ++i)
+ value_checks.push_back(values[i]);
+
+ if (!db.verify_values(value_checks))
+ return false;
+
+ return true;
+}
+
+template<typename key_type, typename value_type>
+bool is_iterator_valid(
+ const typename flat_segment_tree<key_type, value_type>::const_iterator& beg,
+ const typename flat_segment_tree<key_type, value_type>::const_iterator& end, const key_type* keys,
+ const value_type* values, size_t key_size)
+{
+ assert(key_size > 1);
+
+ typedef flat_segment_tree<key_type, value_type> container;
+ typename container::const_iterator itr;
+ size_t idx = 0;
+ for (itr = beg; itr != end; ++itr, ++idx)
+ {
+ if (idx >= key_size)
+ // out-of-bound index
+ return false;
+
+ // Check the key first.
+ if (keys[idx] != itr->first)
+ return false;
+
+ if (idx < key_size - 1)
+ {
+ // Check the value only if it's not the last node. The last node
+ // may have an arbitrary value.
+ if (values[idx] != itr->second)
+ return false;
+ }
+ }
+
+ // At this point, the iterator should be at the end position.
+ if (itr != end)
+ return false;
+
+ // Check the keys and values again but go to the opposite direction.
+ do
+ {
+ --itr;
+ --idx;
+
+ // key
+ if (keys[idx] != itr->first)
+ return false;
+
+ // value
+ if (idx < key_size - 1)
+ {
+ if (values[idx] != itr->second)
+ return false;
+ }
+ } while (itr != beg);
+
+ return true;
+}
+
+template<typename key_type, typename value_type>
+bool is_iterator_valid(
+ const typename flat_segment_tree<key_type, value_type>::const_reverse_iterator& beg,
+ const typename flat_segment_tree<key_type, value_type>::const_reverse_iterator& end, const key_type* keys,
+ const value_type* values, size_t key_size)
+{
+ assert(key_size > 1);
+
+ typedef flat_segment_tree<key_type, value_type> container;
+ typename container::const_reverse_iterator itr;
+ size_t idx = key_size - 1;
+ for (itr = beg; itr != end; ++itr, --idx)
+ {
+ if (idx >= key_size)
+ // out-of-bound index
+ return false;
+
+ // Check the key first.
+ if (keys[idx] != itr->first)
+ return false;
+
+ if (idx < key_size - 1)
+ {
+ // Check the value only if it's not the last node. The last node
+ // may have an arbitrary value.
+ if (values[idx] != itr->second)
+ return false;
+ }
+ }
+
+ // At this point, the iterator should be at the end position.
+ if (itr != end)
+ return false;
+
+ // Check the keys and values again but go to the opposite direction.
+ do
+ {
+ --itr;
+ ++idx;
+
+ // key
+ if (keys[idx] != itr->first)
+ return false;
+
+ // value
+ if (idx < key_size - 1)
+ {
+ if (values[idx] != itr->second)
+ return false;
+ }
+ } while (itr != beg);
+
+ return true;
+}
+
+void fst_test_insert_search_mix()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<int, int> db_type;
+ db_type db(0, 100, 0);
+
+ build_and_dump(db);
+ assert(db_type::node::get_instance_count() == db.leaf_size());
+ assert(db.is_tree_valid());
+ test_single_tree_search(db, 0, 0, 0, 100);
+ test_single_tree_search(db, 99, 0, 0, 100);
+
+ db.insert_front(0, 10, 1);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ assert(db_type::node::get_instance_count() == db.leaf_size());
+ assert(db.is_tree_valid());
+ test_single_tree_search(db, 0, 1, 0, 10);
+ test_single_tree_search(db, 5, 1, 0, 10);
+ test_single_tree_search(db, 9, 1, 0, 10);
+ test_single_tree_search(db, 10, 0, 10, 100);
+
+ db.insert_front(0, 100, 0);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ assert(db_type::node::get_instance_count() == db.leaf_size());
+ assert(db.is_tree_valid());
+ test_single_tree_search(db, 0, 0, 0, 100);
+ test_single_tree_search(db, 99, 0, 0, 100);
+
+ db.insert_front(10, 20, 5);
+ db.insert_front(30, 40, 5);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ assert(db_type::node::get_instance_count() == db.leaf_size());
+ assert(db.is_tree_valid());
+ test_single_tree_search(db, 10, 5, 10, 20);
+ test_single_tree_search(db, 20, 0, 20, 30);
+ test_single_tree_search(db, 30, 5, 30, 40);
+ test_single_tree_search(db, 40, 0, 40, 100);
+
+ db.insert_front(18, 22, 6);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ assert(db_type::node::get_instance_count() == db.leaf_size());
+ assert(db.is_tree_valid());
+ test_single_tree_search(db, 18, 6, 18, 22);
+ test_single_tree_search(db, 22, 0, 22, 30);
+ test_single_tree_search(db, 30, 5, 30, 40);
+
+ db.insert_front(19, 30, 5);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ assert(db_type::node::get_instance_count() == db.leaf_size());
+ assert(db.is_tree_valid());
+ test_single_tree_search(db, 19, 5, 19, 40);
+
+ db.insert_front(-100, 500, 999);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ assert(db_type::node::get_instance_count() == db.leaf_size());
+ assert(db.is_tree_valid());
+ test_single_tree_search(db, 30, 999, 0, 100);
+}
+
+void fst_test_shift_left()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<int, int> db_type;
+ db_type db(0, 100, 0);
+ db.insert_front(20, 40, 5);
+ db.insert_front(50, 60, 10);
+ db.insert_front(70, 80, 15);
+ build_and_dump(db);
+
+ // invalid segment ranges -- these should not modify the state of the
+ // tree, hence the tree should remain valid.
+ db.shift_left(5, 0);
+ assert(db.is_tree_valid());
+
+ db.shift_left(95, 120);
+ assert(db.is_tree_valid());
+
+ db.shift_left(105, 120);
+ assert(db.is_tree_valid());
+
+ db.shift_left(-10, -5);
+ assert(db.is_tree_valid());
+
+ db.shift_left(-10, 5);
+ assert(db.is_tree_valid());
+
+ // shift without removing nodes (including the lower bound).
+ db.shift_left(0, 5);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ std::vector<int> key_checks;
+ key_checks.push_back(0);
+ key_checks.push_back(15);
+ key_checks.push_back(35);
+ key_checks.push_back(45);
+ key_checks.push_back(55);
+ key_checks.push_back(65);
+ key_checks.push_back(75);
+ key_checks.push_back(100);
+ assert(db.verify_keys(key_checks));
+ }
+
+ // shift without removing nodes (not including the lower bound).
+ db.shift_left(1, 6);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ std::vector<int> key_checks;
+ key_checks.push_back(0);
+ key_checks.push_back(10);
+ key_checks.push_back(30);
+ key_checks.push_back(40);
+ key_checks.push_back(50);
+ key_checks.push_back(60);
+ key_checks.push_back(70);
+ key_checks.push_back(100);
+ assert(db.verify_keys(key_checks));
+ }
+
+ // shift without removing nodes (the upper bound of the removed segment
+ // coincides with a node).
+ db.shift_left(5, 10);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ std::vector<int> key_checks;
+ key_checks.push_back(0);
+ key_checks.push_back(5);
+ key_checks.push_back(25);
+ key_checks.push_back(35);
+ key_checks.push_back(45);
+ key_checks.push_back(55);
+ key_checks.push_back(65);
+ key_checks.push_back(100);
+ assert(db.verify_keys(key_checks));
+ }
+
+ // shift with one overlapping node.
+ db.shift_left(1, 11);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 1, 15, 25, 35, 45, 55, 100};
+ int vals[] = {0, 5, 0, 10, 0, 15, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // shift with two overlapping nodes.
+ db.shift_left(2, 30);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 1, 2, 7, 17, 27, 100};
+ int vals[] = {0, 5, 10, 0, 15, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // shift with both ends at existing nodes, but no nodes in between.
+ db.shift_left(0, 1);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 1, 6, 16, 26, 100};
+ int vals[] = {5, 10, 0, 15, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // shift with both ends at existing nodes, no nodes in between, and
+ // removing the segment results in two consecutive segments with identical
+ // value. The segments should get combined into one.
+ db.shift_left(16, 26);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 1, 6, 100};
+ int vals[] = {5, 10, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // insert two new segments for the next test....
+ db.insert_front(10, 20, 400);
+ db.insert_front(30, 40, 400);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 1, 6, 10, 20, 30, 40, 100};
+ int vals[] = {5, 10, 0, 400, 0, 400, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // same test as the previous one, but the value of the combined segment
+ // differs from the value of the rightmost leaf node.
+ db.shift_left(20, 30);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 1, 6, 10, 30, 100};
+ int vals[] = {5, 10, 0, 400, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // remove all.
+ db.shift_left(0, 100);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+}
+
+void fst_test_shift_left_right_edge()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ flat_segment_tree<int, bool> db(0, 100, false);
+ build_and_dump(db);
+
+ // This should not change the tree state.
+ db.shift_left(2, 100);
+ build_and_dump(db);
+ {
+ int keys[] = {0, 100};
+ bool vals[] = {false};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ db.insert_front(20, 100, true);
+ build_and_dump(db);
+ {
+ int keys[] = {0, 20, 100};
+ bool vals[] = {false, true};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // This should insert a new segment at the end with the initial base value.
+ db.shift_left(80, 100);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 20, 80, 100};
+ bool vals[] = {false, true, false};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // This should not modify the tree since the removed segment already has
+ // the initial base value.
+ db.shift_left(85, 100);
+ assert(db.is_tree_valid()); // tree must still be valid.
+ build_and_dump(db);
+ {
+ int keys[] = {0, 20, 80, 100};
+ bool vals[] = {false, true, false};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Insert a new segment at the end with the value 'true' again...
+ db.insert_front(85, 100, true);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 20, 80, 85, 100};
+ bool vals[] = {false, true, false, true};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ db.shift_left(90, 95);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 20, 80, 85, 95, 100};
+ bool vals[] = {false, true, false, true, false};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+}
+
+void fst_test_shift_left_append_new_segment()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ flat_segment_tree<int, bool> db(0, 100, false);
+ db.insert_front(0, 100, true);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 100};
+ bool vals[] = {true};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ db.shift_left(10, 20);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 90, 100};
+ bool vals[] = {true, false};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ db.insert_front(0, 10, true);
+ db.insert_front(10, 20, false);
+ db.insert_front(20, 60, true);
+ db.insert_front(60, 80, false);
+ db.insert_front(80, 100, true);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 10, 20, 60, 80, 100};
+ bool vals[] = {true, false, true, false, true};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ db.shift_left(0, 70);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 10, 30, 100};
+ bool vals[] = {false, true, false};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+}
+
+void fst_test_shift_right_init0()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ flat_segment_tree<int, int> db(0, 100, 0);
+ db.insert_front(0, 10, 15);
+ db.insert_front(10, 20, 1);
+ db.insert_front(20, 30, 2);
+ db.insert_front(30, 40, 3);
+ db.insert_front(40, 50, 4);
+ db.insert_front(50, 60, 5);
+ db.insert_front(60, 70, 6);
+ db.insert_front(70, 80, 7);
+ db.insert_front(80, 90, 8);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+
+ // shifting position is at the lower bound. The leftmost segment has a
+ // non-zero value which needs to be preserved after the shift by adding a
+ // new node.
+ db.shift_right(0, 5, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 5, 15, 25, 35, 45, 55, 65, 75, 85, 95, 100};
+ int vals[] = {0, 15, 1, 2, 3, 4, 5, 6, 7, 8, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // shifting position is at the lower bound, and after the shift, the upper
+ // bound of the last non-zero segment (10) becomes the upper bound of the
+ // global range.
+ db.shift_right(0, 5, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
+ int vals[] = {0, 15, 1, 2, 3, 4, 5, 6, 7, 8};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Shift by some odd number.
+ db.shift_right(0, 49, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 59, 69, 79, 89, 99, 100};
+ int vals[] = {0, 15, 1, 2, 3, 4};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Shift so that the 2nd node from the right-most node becomes the new
+ // right-most node.
+ db.shift_right(0, 11, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 70, 80, 90, 100};
+ int vals[] = {0, 15, 1, 2};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // This should remove all segments.
+ db.shift_right(0, 30, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 100};
+ int vals[] = {0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Insert a few new segments for the next series of tests...
+ db.insert_front(5, 10, 5);
+ db.insert_front(20, 30, 5);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 5, 10, 20, 30, 100};
+ int vals[] = {0, 5, 0, 5, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Inserting at a non-node position. This should simply extend that
+ // segment and shift all the others.
+ db.shift_right(6, 20, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 5, 30, 40, 50, 100};
+ int vals[] = {0, 5, 0, 5, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Inserting at a node position.
+ db.shift_right(5, 20, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 25, 50, 60, 70, 100};
+ int vals[] = {0, 5, 0, 5, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Inserting at a non-node position, pushing a node out-of-bound.
+ db.shift_right(65, 40, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 25, 50, 60, 100};
+ int vals[] = {0, 5, 0, 5};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+
+ // Inserting at a node position, pushing a node out-of-bound.
+ db.shift_right(50, 40, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int keys[] = {0, 25, 90, 100};
+ int vals[] = {0, 5, 0};
+ assert(check_leaf_nodes(db, keys, vals, std::size(keys)));
+ }
+}
+
+void fst_test_shift_right_init999()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ // Initialize the tree with a default value of 999.
+ flat_segment_tree<int, int> db(0, 100, 999);
+ db.insert_front(0, 10, 0);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int k[] = {0, 10, 100};
+ int v[] = {0, 999};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ // This should only extend the first segment.
+ db.shift_right(1, 10, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int k[] = {0, 20, 100};
+ int v[] = {0, 999};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ // Inserting at the leftmost node position should create a new segment
+ // with a default value of 999.
+ db.shift_right(0, 10, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ int k[] = {0, 10, 30, 100};
+ int v[] = {999, 0, 999};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ // Invalid shifts -- these should not invalidate the tree.
+ db.shift_right(-10, 10, false);
+ assert(db.is_tree_valid());
+
+ db.shift_right(100, 10, false);
+ assert(db.is_tree_valid());
+
+ db.shift_right(0, 0, false);
+ assert(db.is_tree_valid());
+}
+
+void fst_test_shift_right_bool()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ flat_segment_tree<long, bool> db(0, 1048576, false);
+ db.insert_front(3, 7, true);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ long k[] = {0, 3, 7, 1048576};
+ bool v[] = {false, true, false};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.shift_right(1, 1, false);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ long k[] = {0, 4, 8, 1048576};
+ bool v[] = {false, true, false};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+}
+
+void fst_test_shift_right_skip_start_node()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ flat_segment_tree<long, short> db(0, 1048576, 0);
+ db.insert_front(3, 7, 5);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ long k[] = {0, 3, 7, 1048576};
+ short v[] = {0, 5, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.shift_right(3, 2, true);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ long k[] = {0, 3, 9, 1048576};
+ short v[] = {0, 5, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ // shift_right from the leftmost node should not change its value
+ db.insert_front(0, 4, 2);
+ assert(!db.is_tree_valid());
+ build_and_dump(db);
+ {
+ long k[] = {0, 4, 9, 1048576};
+ short v[] = {2, 5, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.shift_right(0, 2, true);
+ build_and_dump(db);
+ {
+ long k[] = {0, 6, 11, 1048576};
+ short v[] = {2, 5, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+}
+
+/**
+ * Right all nodes right so that all existing nodes get pushed out of the
+ * range.
+ */
+void fst_test_shift_right_all_nodes()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<unsigned, unsigned> fst_type;
+
+ fst_type db(0, 10, 0);
+ {
+ unsigned k[] = {0, 10};
+ unsigned v[] = {0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(0, 8, 2);
+ db.dump_leaf_nodes();
+ {
+ unsigned k[] = {0, 8, 10};
+ unsigned v[] = {2, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ // Shift all nodes out of range. After this, there should be only the
+ // left and right most nodes left.
+ db.shift_right(0, 15, false);
+ db.dump_leaf_nodes();
+ {
+ unsigned k[] = {0, 10};
+ unsigned v[] = {0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+}
+
+template<typename key_type, typename value_type>
+struct leaf_node_functor
+{
+ void operator()(const std::pair<key_type, value_type>&) const
+ {}
+};
+
+void fst_test_const_iterator()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ {
+ typedef unsigned int key_type;
+ typedef unsigned short value_type;
+ unsigned short max_value = std::numeric_limits<value_type>::max();
+ typedef flat_segment_tree<key_type, value_type> container_type;
+
+ container_type db(0, 1000, max_value);
+
+ build_and_dump(db);
+ {
+ unsigned int k[] = {0, 1000};
+ unsigned short v[] = {max_value};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_front(10, 20, 10);
+ db.insert_front(20, 50, 20);
+ db.insert_front(100, 300, 55);
+ build_and_dump(db);
+ {
+ unsigned int k[] = {0, 10, 20, 50, 100, 300, 1000};
+ unsigned short v[] = {max_value, 10, 20, max_value, 55, max_value};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ fprintf(stdout, "fst_test_const_iterator: leaf nodes valid\n");
+
+ // Check the forward iterator's integrity.
+ assert(is_iterator_valid(db.begin(), db.end(), k, v, std::size(k)));
+ fprintf(stdout, "fst_test_const_iterator: forward iterator valid\n");
+
+ // Check the reverse iterator's integrity.
+ assert(is_iterator_valid(db.rbegin(), db.rend(), k, v, std::size(k)));
+ fprintf(stdout, "fst_test_const_iterator: reverse iterator valid\n");
+ }
+
+ // Make sure it works with for_each.
+ std::for_each(db.begin(), db.end(), leaf_node_functor<key_type, value_type>());
+ }
+
+ {
+ typedef flat_segment_tree<int, bool> container_type;
+ container_type db(0, 100, true);
+ db.insert_front(0, 50, false);
+
+ {
+ cout << "-- forward" << endl;
+ container_type::const_iterator it = db.begin(), it_end = db.end();
+ // 0 -> 50 -> 100 -> end
+ cout << "key: " << it->first << " value: " << it->second << endl;
+ assert(it->first == 0);
+ assert(it->second == false);
+ ++it;
+ cout << "key: " << it->first << " value: " << it->second << endl;
+ assert(it->first == 50);
+ assert(it->second == true);
+ ++it;
+ cout << "key: " << it->first << " value: " << it->second << endl;
+ assert(it->first == 100);
+ assert(it != it_end);
+ ++it;
+ assert(it == it_end);
+ }
+ {
+ cout << "-- reverse" << endl;
+ container_type::const_reverse_iterator it = db.rbegin(), it_end = db.rend();
+ // 100 -> 50 -> 0 -> end
+ cout << "key: " << it->first << " value: " << it->second << endl;
+ assert(it->first == 100);
+ ++it;
+ cout << "key: " << it->first << " value: " << it->second << endl;
+ assert(it->first == 50);
+ assert(it->second == true);
+ ++it;
+ cout << "key: " << it->first << " value: " << it->second << endl;
+ assert(it->first == 0);
+ assert(it->second == false);
+ assert(it != it_end);
+ ++it;
+ assert(it == it_end);
+ }
+ }
+}
+
+template<typename key_type, typename value_type>
+void fst_test_insert_front_back(key_type start_key, key_type end_key, value_type default_value)
+{
+ MDDS_TEST_FUNC_SCOPE_MSG(
+ "start-key=" << start_key << "; end-key=" << end_key << "; default-value=" << default_value);
+
+ typedef flat_segment_tree<key_type, value_type> container_type;
+ typedef typename container_type::const_iterator itr_type;
+
+ value_type val = 0;
+
+ // insert a series of segments from the front.
+ container_type db_front(start_key, end_key, default_value);
+ for (key_type i = start_key; i < end_key - 10; ++i)
+ {
+ itr_type itr = db_front.insert_front(i, i + 1, val).first;
+ assert(itr->first == i);
+ assert(itr->second == val);
+ if (++val > 10)
+ val = 0;
+ }
+
+ // insert the same series of segments from the back.
+ container_type db_back(start_key, end_key, default_value);
+ val = 0;
+ for (key_type i = start_key; i < end_key - 10; ++i)
+ {
+ itr_type itr = db_back.insert_back(i, i + 1, val).first;
+ assert(itr->first == i);
+ assert(itr->second == val);
+ if (++val > 10)
+ val = 0;
+ }
+
+ // Now, these two must be identical.
+ if (db_front != db_back)
+ {
+ // They are not identical!
+ db_front.dump_leaf_nodes();
+ db_back.dump_leaf_nodes();
+ cout << "start_key = " << start_key << " end_key = " << end_key << " default_value = " << default_value
+ << endl;
+ assert(!"Contents of the two containers are not identical!");
+ }
+}
+
+void fst_perf_test_insert_front_back()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef unsigned long key_type;
+ typedef int value_type;
+ typedef flat_segment_tree<key_type, value_type> container_type;
+ key_type upper_bound = 20000;
+ {
+ stack_printer __stack_printer__("::fst_perf_test_insert (front insertion)");
+ container_type db(0, upper_bound, 0);
+ value_type val = 0;
+ for (key_type i = 0; i < upper_bound; ++i)
+ {
+ db.insert_front(i, i + 1, val);
+ if (++val > 10)
+ val = 0;
+ }
+ }
+
+ {
+ stack_printer __stack_printer__("::fst_perf_test_insert (back insertion)");
+ container_type db(0, upper_bound, 0);
+ value_type val = 0;
+ for (key_type i = 0; i < upper_bound; ++i)
+ {
+ db.insert_back(i, i + 1, val);
+ if (++val > 10)
+ val = 0;
+ }
+ }
+}
+
+void fst_test_copy_ctor()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef unsigned long key_type;
+ typedef int value_type;
+ typedef flat_segment_tree<key_type, value_type> fst;
+
+ // Test copy construction of node first.
+
+ {
+ // Original node.
+ fst::node_ptr node1(new fst::node);
+ node1->value_leaf.key = 10;
+ node1->value_leaf.value = 500;
+ assert(node1->is_leaf);
+ assert(!node1->parent);
+ assert(!node1->prev);
+ assert(!node1->next);
+
+ // Copy it to new node.
+ fst::node_ptr node2(new fst::node(*node1));
+ assert(node2->is_leaf);
+ assert(!node2->parent);
+ assert(!node2->prev);
+ assert(!node2->next);
+ assert(node2->value_leaf.key == 10);
+ assert(node2->value_leaf.value == 500);
+
+ // Changing the values of the original should not modify the second node.
+ node1->value_leaf.key = 35;
+ node1->value_leaf.value = 200;
+ assert(node2->value_leaf.key == 10);
+ assert(node2->value_leaf.value == 500);
+ }
+
+ {
+ // Test non-leaf node objects.
+ fst::nonleaf_node node1;
+ node1.value_nonleaf.low = 123;
+ node1.value_nonleaf.high = 789;
+
+ // Test the copying of non-leaf values.
+ fst::nonleaf_node node2(node1);
+ assert(!node2.is_leaf);
+ assert(!node2.parent);
+ assert(!node2.left);
+ assert(!node2.right);
+ assert(node2.value_nonleaf.low == 123);
+ assert(node2.value_nonleaf.high == 789);
+ }
+
+ // Now, test the copy construction of the flat_segment_tree.
+
+ // Simple copying by copy construction.
+ fst db(0, 100, 5);
+ fst db_copied(db);
+ assert(db == db_copied);
+ {
+ key_type k[] = {0, 100};
+ value_type v[] = {5};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ // Inserting the same segment value to both instances. They should still
+ // be equal.
+ db.insert_front(5, 10, 0);
+ db_copied.insert_front(5, 10, 0);
+ assert(db == db_copied);
+ {
+ key_type k[] = {0, 5, 10, 100};
+ value_type v[] = {5, 0, 5};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ // Inserting a new segment only to the 2nd instance. They should differ.
+ db_copied.insert_front(15, 20, 35);
+ assert(db != db_copied);
+ {
+ key_type k[] = {0, 5, 10, 15, 20, 100};
+ value_type v[] = {5, 0, 5, 35, 5};
+ assert(check_leaf_nodes(db_copied, k, v, std::size(k)));
+ }
+
+ // Make sure that copying will leave the tree invalid.
+ assert(!db_copied.is_tree_valid());
+ db_copied.build_tree();
+ assert(db_copied.is_tree_valid());
+ fst db_copied_again(db_copied);
+ assert(db_copied == db_copied_again);
+ assert(!db_copied_again.is_tree_valid());
+ assert(!db_copied_again.get_root_node());
+
+ // Make sure we can still perform tree search correctly.
+ value_type answer = 0;
+ db_copied_again.build_tree();
+ db_copied_again.search_tree(18, answer);
+ assert(db_copied_again.is_tree_valid());
+ assert(answer == 35);
+}
+
+void fst_test_move_ctor()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ {
+ // initial condition (2 nodes)
+ using container_type = mdds::flat_segment_tree<int64_t, std::string>;
+ container_type src(-50, 50, "none");
+
+ // pointer to the root node should stay the same before and after the move.
+ auto src_root = src.get_root_node();
+
+ container_type moved(std::move(src));
+ assert(moved.min_key() == -50);
+ assert(moved.max_key() == 50);
+ assert(moved.default_value() == "none");
+ assert(moved.leaf_size() == 2);
+ assert(!moved.is_tree_valid());
+ assert(moved.get_root_node() == src_root);
+
+ moved.build_tree();
+ assert(moved.is_tree_valid());
+
+ {
+ // Make sure search_tree() won't access invalid memory
+ std::string v;
+ moved.search_tree(0, v);
+ assert(v == "none");
+ }
+
+ src_root = moved.get_root_node();
+
+ // move again with valid tree
+ container_type moved2(std::move(moved));
+ assert(moved2.min_key() == -50);
+ assert(moved2.max_key() == 50);
+ assert(moved2.default_value() == "none");
+ assert(moved2.leaf_size() == 2);
+ assert(moved2.is_tree_valid());
+ assert(src_root == moved2.get_root_node());
+
+ {
+ // Make sure search_tree() won't access invalid memory
+ std::string v;
+ moved2.search_tree(0, v);
+ assert(v == "none");
+ }
+ }
+
+ {
+ // 4 nodes
+ using container_type = mdds::flat_segment_tree<int64_t, std::string>;
+ container_type src(-50, 50, "none");
+ src.insert_back(-10, 10, "middle");
+
+ // pointer to the root node should stay the same before and after the move.
+ auto src_root = src.get_root_node();
+
+ container_type moved(std::move(src));
+ assert(moved.min_key() == -50);
+ assert(moved.max_key() == 50);
+ assert(moved.default_value() == "none");
+ assert(moved.leaf_size() == 4);
+ assert(!moved.is_tree_valid());
+ assert(moved.get_root_node() == src_root);
+
+ moved.build_tree();
+ assert(moved.is_tree_valid());
+
+ {
+ // Make sure search_tree() won't access invalid memory
+ std::string v;
+ moved.search_tree(-40, v);
+ assert(v == "none");
+
+ moved.search_tree(0, v);
+ assert(v == "middle");
+ }
+
+ src_root = moved.get_root_node();
+
+ // move again with valid tree
+ container_type moved2(std::move(moved));
+ assert(moved2.min_key() == -50);
+ assert(moved2.max_key() == 50);
+ assert(moved2.default_value() == "none");
+ assert(moved2.leaf_size() == 4);
+ assert(moved2.is_tree_valid());
+ assert(src_root == moved2.get_root_node());
+
+ {
+ // Make sure search_tree() won't access invalid memory
+ std::string v;
+ moved2.search_tree(-40, v);
+ assert(v == "none");
+
+ moved2.search_tree(0, v);
+ assert(v == "middle");
+ }
+ }
+}
+
+void fst_test_equality()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef unsigned long key_type;
+ typedef int value_type;
+ typedef flat_segment_tree<key_type, value_type> container_type;
+
+ container_type db1(0, 100, 0);
+ container_type db2(0, 100, 0);
+ assert(db1 == db2);
+
+ db1.insert_front(0, 1, 1);
+ assert(db1 != db2);
+
+ db2.insert_front(0, 1, 1);
+ assert(db1 == db2);
+
+ // Same node count, but with different value.
+ db2.insert_front(0, 1, 2);
+ assert(db1 != db2);
+
+ // Set the value back.
+ db2.insert_front(0, 1, 1);
+ assert(db1 == db2);
+
+ db1.insert_front(4, 10, 10);
+ db1.insert_front(4, 10, 0);
+ assert(db1 == db2);
+
+ db1.insert_front(20, 40, 5);
+ db1.insert_front(30, 35, 6);
+ assert(db1 != db2);
+
+ db2.insert_front(20, 30, 5);
+ db2.insert_front(30, 35, 6);
+ db2.insert_front(35, 40, 5);
+ assert(db1 == db2);
+}
+
+void fst_test_back_insert()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef unsigned int key_type;
+ typedef unsigned short value_type;
+ typedef flat_segment_tree<key_type, value_type> container_type;
+ container_type db(0, 100, 0);
+ db.insert_back(1, 2, 1);
+ {
+ unsigned int k[] = {0, 1, 2, 100};
+ unsigned short v[] = {0, 1, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(3, 4, 2);
+ {
+ unsigned int k[] = {0, 1, 2, 3, 4, 100};
+ unsigned short v[] = {0, 1, 0, 2, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(4, 5, 2);
+ {
+ unsigned int k[] = {0, 1, 2, 3, 5, 100};
+ unsigned short v[] = {0, 1, 0, 2, 0};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(90, 120, 10);
+ {
+ unsigned int k[] = {0, 1, 2, 3, 5, 90, 100};
+ unsigned short v[] = {0, 1, 0, 2, 0, 10};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(0, 10, 20);
+ {
+ unsigned int k[] = {0, 10, 90, 100};
+ unsigned short v[] = {20, 0, 10};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(5, 20, 20);
+ {
+ unsigned int k[] = {0, 20, 90, 100};
+ unsigned short v[] = {20, 0, 10};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(15, 30, 5);
+ {
+ unsigned int k[] = {0, 15, 30, 90, 100};
+ unsigned short v[] = {20, 5, 0, 10};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.insert_back(0, 1, 2);
+ {
+ unsigned int k[] = {0, 1, 15, 30, 90, 100};
+ unsigned short v[] = {2, 20, 5, 0, 10};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+
+ db.dump_leaf_nodes();
+}
+
+template<typename A, typename B>
+void print_iterator(typename flat_segment_tree<A, B>::const_iterator& itr)
+{
+ cout << "iterator: (key=" << itr->first << ",value=" << itr->second << ")" << endl;
+}
+
+void fst_test_insert_iterator()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef long key_type;
+ typedef short value_type;
+ typedef flat_segment_tree<key_type, value_type> db_type;
+
+ db_type db(0, 100, 0);
+ db_type::const_iterator itr;
+
+ itr = db.insert_front(0, 5, 4).first;
+ assert(itr->first == 0);
+ assert(itr->second == 4);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(3, 10, 100).first;
+ assert(itr->first == 3);
+ assert(itr->second == 100);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(5, 8, 100).first;
+ assert(itr->first == 3);
+ assert(itr->second == 100);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(5, 8, 50).first;
+ assert(itr->first == 5);
+ assert(itr->second == 50);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(6, 9, 50).first;
+ assert(itr->first == 5);
+ assert(itr->second == 50);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(9, 20, 24).first;
+ assert(itr->first == 9);
+ assert(itr->second == 24);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(19, 24, 34).first;
+ assert(itr->first == 19);
+ assert(itr->second == 34);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(24, 26, 0).first;
+ assert(itr->first == 24);
+ assert(itr->second == 0);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(30, 50, 2).first;
+ assert(itr->first == 30);
+ assert(itr->second == 2);
+ print_iterator<key_type, value_type>(itr);
+
+ itr = db.insert_front(120, 140, 34).first;
+ assert(itr == db.end());
+
+ itr = db.insert_front(-20, -10, 20).first;
+ assert(itr == db.end());
+}
+
+void fst_test_insert_state_changed()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef long key_type;
+ typedef short value_type;
+ typedef flat_segment_tree<key_type, value_type> db_type;
+ typedef std::pair<db_type::const_iterator, bool> ret_type;
+
+ db_type db(0, 1000, 0);
+
+ // Inserting a segment with the default value. This should not change the
+ // state.
+ ret_type r = db.insert_front(10, 15, 0);
+ assert(!r.second);
+
+ // New segment with a different value.
+ r = db.insert_front(0, 10, 1);
+ assert(r.second);
+
+ // Inserting the same segment should not change the state.
+ r = db.insert_front(0, 10, 1);
+ assert(!r.second);
+
+ r = db.insert_front(0, 1, 1);
+ assert(!r.second);
+
+ r = db.insert_front(8, 10, 1);
+ assert(!r.second);
+
+ // This extends the segment, therefore the state should change.
+ r = db.insert_front(8, 11, 1);
+ assert(r.second);
+
+ r = db.insert_front(11, 15, 0);
+ assert(!r.second);
+
+ // This extends the segment. At this point, 0 - 15 should have a value of 1.
+ r = db.insert_front(11, 15, 1);
+ assert(r.second);
+ {
+ db_type::const_iterator itr = r.first;
+ assert(itr->first == 0);
+ assert(itr->second == 1);
+ ++itr;
+ assert(itr->first == 15);
+ }
+
+ r = db.insert_front(2, 4, 1);
+ assert(!r.second);
+
+ // Different value segment. This should change the state.
+ r = db.insert_front(2, 4, 0);
+ assert(r.second);
+
+ // Ditto.
+ r = db.insert_front(2, 4, 1);
+ assert(r.second);
+
+ r = db.insert_front(1, 8, 1);
+ assert(!r.second);
+
+ // Different value segment.
+ r = db.insert_front(1, 8, 2);
+ assert(r.second);
+
+ r = db.insert_front(8, 20, 2);
+ assert(r.second);
+
+ // The 0-1 segment should still have a value of 1. So this won't change
+ // the state.
+ r = db.insert_front(0, 1, 1);
+ assert(!r.second);
+
+ // Partially out-of-bound segment, but this should modify the value of 0-2.
+ r = db.insert_front(-50, 2, 10);
+ assert(r.second);
+ {
+ db_type::const_iterator itr = r.first;
+ assert(itr->first == 0);
+ assert(itr->second == 10);
+ ++itr;
+ assert(itr->first == 2);
+ }
+
+ // Entirely out-of-bound.
+ r = db.insert_front(-50, -2, 20);
+ assert(!r.second);
+
+ // Likewise, partially out-of-bound at the higher end.
+ r = db.insert_front(800, 1200, 20);
+ assert(r.second);
+
+ // Entirely out-of-bound.
+ r = db.insert_front(1300, 1400, 25);
+ assert(!r.second);
+}
+
+void fst_perf_test_insert_position()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, bool> db_type;
+ typedef std::pair<db_type::const_iterator, bool> ret_type;
+ long upper = 60000;
+ {
+ stack_printer __stack_printer__("::fst_perf_test_insert_position (front)");
+ // Much smaller upper boundary because front insertion is very slow.
+ db_type db(0, upper, false);
+ bool val = false;
+ for (long i = 0; i < upper; ++i)
+ {
+ db.insert_front(i, i + 1, val);
+ val = !val;
+ }
+ }
+
+ {
+ stack_printer __stack_printer__("::fst_perf_test_insert_position (back)");
+ db_type db(0, upper, false);
+ bool val = false;
+ for (long i = 0; i < upper; ++i)
+ {
+ db.insert_back(i, i + 1, val);
+ val = !val;
+ }
+ }
+
+ {
+ db_type db(0, upper, false);
+ {
+ stack_printer __stack_printer__("::fst_perf_test_insert_position (position)");
+ db_type::const_iterator itr = db.begin();
+ bool val = false;
+ for (long i = 0; i < upper; ++i)
+ {
+ ret_type ret = db.insert(itr, i, i + 1, val);
+ val = !val;
+ itr = ret.first;
+ }
+ }
+ {
+ stack_printer __stack_printer__("::fst_perf_test_insert_position (position re-insert)");
+ db_type::const_iterator itr = db.begin();
+ bool val = true;
+ for (long i = 0; i < upper; ++i)
+ {
+ ret_type ret = db.insert(itr, i, i + 1, val);
+ val = !val;
+ itr = ret.first;
+ }
+ }
+ }
+}
+
+void fst_perf_test_position_search()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, bool> db_type;
+ typedef std::pair<db_type::const_iterator, bool> ret_type;
+ long upper = 60000;
+ db_type db(0, upper, false);
+
+ // Fill the leaf nodes first.
+ db_type::const_iterator itr = db.begin();
+ bool val = false;
+ for (long i = 0; i < upper; ++i)
+ {
+ ret_type ret = db.insert(itr, i, i + 1, val);
+ val = !val;
+ itr = ret.first;
+ }
+
+ {
+ stack_printer __stack_printer__("::fst_perf_test_position_search (normal)");
+ for (long i = 0; i < upper; ++i)
+ {
+ bool val2;
+ ret_type ret = db.search(i, val2);
+ assert(ret.second);
+ }
+ }
+
+ {
+ stack_printer __stack_printer__("::fst_perf_test_position_search (positioned)");
+ itr = db.begin();
+ for (long i = 0; i < upper; ++i)
+ {
+ bool val2;
+ ret_type ret = db.search(itr, i, val2);
+ assert(ret.second);
+ itr = ret.first;
+ }
+ }
+}
+
+template<typename K, typename V>
+bool check_pos_search_result(
+ const flat_segment_tree<K, V>& db, typename flat_segment_tree<K, V>::const_iterator& itr, K key, K start_expected,
+ K end_expected, V value_expected)
+{
+ typedef flat_segment_tree<K, V> db_type;
+ typedef std::pair<typename db_type::const_iterator, bool> ret_type;
+
+ V _val;
+ K _start = -1, _end = -1;
+
+ ret_type r = db.search(itr, key, _val, &_start, &_end);
+
+ cout << "expected: start=" << start_expected << " end=" << end_expected << " value=" << value_expected << endl;
+ cout << "observed: start=" << _start << " end=" << _end << " value=" << _val << endl;
+
+ bool result = _start == start_expected && _end == end_expected && _val == value_expected &&
+ r.first->first == start_expected && r.first->second == value_expected;
+ itr = r.first;
+ return result;
+}
+
+void fst_test_position_search()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, short> db_type;
+ typedef std::pair<db_type::const_iterator, bool> ret_type;
+
+ db_type db(0, 100, 0);
+ db.insert_front(10, 20, 1);
+ db.insert_front(30, 50, 5);
+
+ db_type db2(-10, 10, 1);
+
+ struct
+ {
+ long start_range;
+ long end_range;
+ short value_expected;
+ } params[] = {{0, 10, 0}, {10, 20, 1}, {20, 30, 0}, {30, 50, 5}, {50, 100, 0}};
+
+ size_t n = std::size(params);
+
+ cout << "Testing for searches with various valid and invalid iterators." << endl;
+ for (size_t i = 0; i < n; ++i)
+ {
+ for (long j = params[i].start_range; j < params[i].end_range; ++j)
+ {
+ db_type::const_iterator itr;
+ bool success = false;
+
+ // empty iterator - should fall back to normal search.
+ success = check_pos_search_result(
+ db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
+ assert(success);
+
+ // iterator returned from the previous search.
+ success = check_pos_search_result(
+ db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
+ assert(success);
+
+ // begin iterator.
+ itr = db.begin();
+ success = check_pos_search_result(
+ db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
+ assert(success);
+
+ // end iterator.
+ itr = db.end();
+ success = check_pos_search_result(
+ db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
+ assert(success);
+
+ // iterator from another container - should fall back to normal search.
+ itr = db2.begin();
+ success = check_pos_search_result(
+ db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
+ assert(success);
+ }
+ }
+
+ cout << "Testing for continuous searching by re-using the iteraotr from the previous search." << endl;
+ db_type::const_iterator itr;
+ short val;
+ long start = 0, end = 0;
+
+ for (size_t i = 0; i < n; ++i)
+ {
+ ret_type r = db.search(itr, end, val, &start, &end);
+ assert(start == params[i].start_range);
+ assert(end == params[i].end_range);
+ assert(val == params[i].value_expected);
+ assert(r.second);
+ itr = r.first;
+ }
+}
+
+void fst_test_min_max_default()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, short> db_type;
+ db_type db(0, 100, 2);
+ assert(db.min_key() == 0);
+ assert(db.max_key() == 100);
+ assert(db.default_value() == 2);
+}
+
+void fst_test_swap()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, int> db_type;
+ db_type db1(0, 200, 20);
+ db_type db2(20, 40, 0);
+ db1.insert_back(20, 30, 1);
+ db1.insert_back(30, 40, 2);
+ db1.insert_back(40, 50, 3);
+ db1.build_tree();
+
+ // Check the content of db1.
+ {
+ db_type::key_type k[] = {0, 20, 30, 40, 50, 200};
+ db_type::value_type v[] = {20, 1, 2, 3, 20};
+ assert(check_leaf_nodes(db1, k, v, std::size(k)));
+ }
+ assert(db1.min_key() == 0);
+ assert(db1.max_key() == 200);
+ assert(db1.default_value() == 20);
+ assert(db1.is_tree_valid());
+
+ db1.swap(db2);
+
+ // Now db2 should inherit the content of db1.
+ {
+ db_type::key_type k[] = {0, 20, 30, 40, 50, 200};
+ db_type::value_type v[] = {20, 1, 2, 3, 20};
+ assert(check_leaf_nodes(db2, k, v, std::size(k)));
+ }
+ assert(db2.min_key() == 0);
+ assert(db2.max_key() == 200);
+ assert(db2.default_value() == 20);
+ assert(db2.is_tree_valid());
+
+ // Tree search should work on db2.
+ db_type::value_type val = 0;
+ assert(db2.search_tree(35, val).second);
+ assert(val == 2);
+}
+
+void fst_test_swap_tree_memory()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, int> db_type;
+ auto db1 = std::make_unique<db_type>(0, 100, 0);
+ db1->insert_back(10, 40, 999);
+ db1->build_tree();
+ int value = -1;
+ db1->search_tree(20, value);
+ assert(value == 999);
+
+ db_type db2(-10, 10, -99);
+ db2.swap(*db1);
+
+ db1.reset();
+
+ // Make sure that the tree is valid, and you can still search through the tree.
+ assert(db2.is_tree_valid());
+ value = -1;
+ db2.search_tree(20, value);
+ assert(value == 999);
+}
+
+void fst_test_clear()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, int> db_type;
+ db_type db(0, 100, 42);
+ db.insert_back(0, 10, 0);
+ db.insert_back(10, 20, 1);
+ db.insert_back(20, 30, 2);
+ db.build_tree();
+
+ {
+ db_type::key_type k[] = {0, 10, 20, 30, 100};
+ db_type::value_type v[] = {0, 1, 2, 42};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+ assert(db.min_key() == 0);
+ assert(db.max_key() == 100);
+ assert(db.default_value() == 42);
+ assert(db.is_tree_valid());
+
+ db.clear();
+
+ {
+ db_type::key_type k[] = {0, 100};
+ db_type::value_type v[] = {42};
+ assert(check_leaf_nodes(db, k, v, std::size(k)));
+ }
+ assert(db.min_key() == 0);
+ assert(db.max_key() == 100);
+ assert(db.default_value() == 42);
+ assert(!db.is_tree_valid());
+}
+
+void fst_test_assignment()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<long, int> db_type;
+ db_type db1(0, 100, 42);
+ db1.insert_back(0, 10, 0);
+ db1.insert_back(10, 20, 1);
+ db1.insert_back(20, 30, 2);
+ db1.build_tree();
+
+ {
+ db_type::key_type k[] = {0, 10, 20, 30, 100};
+ db_type::value_type v[] = {0, 1, 2, 42};
+ assert(check_leaf_nodes(db1, k, v, std::size(k)));
+ }
+ assert(db1.min_key() == 0);
+ assert(db1.max_key() == 100);
+ assert(db1.default_value() == 42);
+ assert(db1.is_tree_valid());
+
+ db_type db2(20, 40, 0);
+ db2.insert_back(20, 30, 8);
+ db2.build_tree();
+
+ {
+ db_type::key_type k[] = {20, 30, 40};
+ db_type::value_type v[] = {8, 0};
+ assert(check_leaf_nodes(db2, k, v, std::size(k)));
+ }
+ assert(db2.min_key() == 20);
+ assert(db2.max_key() == 40);
+ assert(db2.default_value() == 0);
+ assert(db2.is_tree_valid());
+
+ db_type db3(10, 80, 4);
+ db3.build_tree();
+
+ {
+ db_type::key_type k[] = {10, 80};
+ db_type::value_type v[] = {4};
+ assert(check_leaf_nodes(db3, k, v, std::size(k)));
+ }
+ assert(db3.min_key() == 10);
+ assert(db3.max_key() == 80);
+ assert(db3.default_value() == 4);
+ assert(db3.is_tree_valid());
+
+ db3 = db2 = db1;
+
+ {
+ db_type::key_type k[] = {0, 10, 20, 30, 100};
+ db_type::value_type v[] = {0, 1, 2, 42};
+ assert(check_leaf_nodes(db1, k, v, std::size(k)));
+ }
+ assert(db1.min_key() == 0);
+ assert(db1.max_key() == 100);
+ assert(db1.default_value() == 42);
+ assert(db1.is_tree_valid());
+
+ {
+ db_type::key_type k[] = {0, 10, 20, 30, 100};
+ db_type::value_type v[] = {0, 1, 2, 42};
+ assert(check_leaf_nodes(db2, k, v, std::size(k)));
+ }
+ assert(db2.min_key() == 0);
+ assert(db2.max_key() == 100);
+ assert(db2.default_value() == 42);
+ assert(!db2.is_tree_valid());
+
+ {
+ db_type::key_type k[] = {0, 10, 20, 30, 100};
+ db_type::value_type v[] = {0, 1, 2, 42};
+ assert(check_leaf_nodes(db3, k, v, std::size(k)));
+ }
+ assert(db3.min_key() == 0);
+ assert(db3.max_key() == 100);
+ assert(db3.default_value() == 42);
+ assert(!db3.is_tree_valid());
+}
+
+void fst_test_move_assignment()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ using container_type = flat_segment_tree<uint32_t, std::string>;
+ container_type src{0, 100, "base"};
+ container_type moved{10, 200, "base2"};
+ moved = std::move(src);
+
+ assert(moved.min_key() == 0);
+ assert(moved.max_key() == 100);
+ assert(moved.default_value() == "base");
+ assert(moved.leaf_size() == 2);
+ assert(!moved.is_tree_valid());
+
+ moved.insert_back(10, 25, "10-25");
+ moved.build_tree();
+ assert(moved.is_tree_valid());
+ assert(moved.leaf_size() == 4);
+
+ container_type moved2{30, 450, "base3"};
+ moved2 = std::move(moved);
+ assert(moved2.min_key() == 0);
+ assert(moved2.max_key() == 100);
+ assert(moved2.default_value() == "base");
+ assert(moved2.leaf_size() == 4);
+ assert(moved2.is_tree_valid());
+
+ // Make sure we can perform tree search.
+ std::string v;
+ uint32_t key1, key2;
+ auto res = moved2.search_tree(20, v, &key1, &key2);
+ assert(res.second);
+ assert(v == "10-25");
+ assert(key1 == 10);
+ assert(key2 == 25);
+}
+
+void fst_test_non_numeric_value()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<int, std::string> db_type;
+ db_type db(0, 4, "42");
+ db.insert_back(1, 2, "hello world");
+
+ assert(db.default_value() == "42");
+
+ std::string result;
+ db.search(1, result);
+
+ assert(result == "hello world");
+
+ db_type db2(db);
+
+ assert(db == db2);
+}
+
+void fst_test_insert_out_of_bound()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<int, bool> db_type;
+ db_type db(0, 10, false);
+
+ // An out-of-bound range, whether it's in part or in its entirety, should
+ // be handled gracefully without throwing exceptions or causing segfaults.
+
+ // ranges that are entirely out-of-bound.
+
+ auto ret = db.insert_front(-10, -8, false);
+ assert(!ret.second);
+ db.insert_back(12, 13, false);
+ assert(!ret.second);
+
+ db_type::const_iterator pos = db.end();
+
+ ret = db.insert(pos, -10, -8, false);
+ assert(!ret.second);
+ pos = ret.first;
+
+ ret = db.insert(pos, 12, 13, false);
+ assert(!ret.second);
+ pos = ret.first;
+
+ // partial overflows.
+
+ ret = db.insert(pos, -2, 2, true);
+ assert(ret.second); // content modified
+ pos = ret.first;
+
+ ret = db.insert(pos, 8, 20, true);
+ assert(ret.second); // content modified
+ pos = ret.first;
+}
+
+void fst_test_insert_out_of_bound_2()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<int, bool> db_type;
+ db_type db(0, 256, false);
+
+ // The range is entirely out-of-bound, but the start range equals the
+ // upper bound of the valid range.
+ auto ret = db.insert_back(256, 1024, true);
+
+ // Insertion never took place.
+ assert(ret.first == db.end());
+ assert(!ret.second);
+}
+
+void fst_test_segment_iterator()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ typedef flat_segment_tree<int16_t, bool> db_type;
+ db_type db(0, 100, false);
+
+ db_type::const_segment_iterator it = db.begin_segment();
+ db_type::const_segment_iterator ite = db.end_segment();
+
+ assert(it != ite);
+ assert(it->start == 0);
+ assert(it->end == 100);
+ assert(it->value == false);
+
+ const auto& v = *it;
+ assert(v.start == 0);
+ assert(v.end == 100);
+ assert(v.value == false);
+
+ ++it;
+ assert(it == ite);
+
+ --it;
+ assert(it != ite);
+ assert(it->start == 0);
+ assert(it->end == 100);
+ assert(it->value == false);
+
+ db_type::const_segment_iterator it2; // default constructor
+ it2 = it; // assignment operator
+ assert(it2 == it);
+ assert(it2->start == 0);
+ assert(it2->end == 100);
+ assert(it2->value == false);
+
+ auto it3(it2); // copy constructor
+ assert(it3 == it2);
+ assert(it3->start == 0);
+ assert(it3->end == 100);
+ assert(it3->value == false);
+
+ db.insert_back(20, 50, true); // this invalidates the iterators.
+
+ it = db.begin_segment();
+ ite = db.end_segment();
+
+ assert(it->start == 0);
+ assert(it->end == 20);
+ assert(it->value == false);
+
+ it2 = it++; // post-increment
+
+ assert(it2->start == 0);
+ assert(it2->end == 20);
+ assert(it2->value == false);
+
+ assert(it->start == 20);
+ assert(it->end == 50);
+ assert(it->value == true);
+
+ ++it;
+ assert(it->start == 50);
+ assert(it->end == 100);
+ assert(it->value == false);
+
+ ++it;
+ assert(it == ite);
+
+ it2 = it--; // post-decrement.
+ assert(it2 == ite);
+
+ it = db.begin_segment();
+ auto it_moved{std::move(it)}; // move construction
+
+ assert(it_moved->start == 0);
+ assert(it_moved->end == 20);
+ assert(it_moved->value == false);
+}
+
+void fst_test_segment_range()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ using container_type = mdds::flat_segment_tree<int32_t, std::string>;
+ using node_type = container_type::const_segment_iterator::value_type;
+
+ {
+ container_type db{0, 100, "-"};
+
+ const std::vector<node_type> expected = {
+ {0, 100, "-"},
+ };
+
+ std::cout << "--" << std::endl;
+
+ std::vector<node_type> actual;
+ for (const node_type& v : db.segment_range())
+ {
+ std::cout << "start=" << v.start << "; end=" << v.end << "; value='" << v.value << "'" << std::endl;
+ actual.push_back(v);
+ }
+
+ assert(expected == actual);
+ }
+
+ {
+ container_type db{0, 100, "-"};
+ db.insert_back(10, 25, "10-25");
+
+ const std::vector<node_type> expected = {
+ {0, 10, "-"},
+ {10, 25, "10-25"},
+ {25, 100, "-"},
+ };
+
+ std::cout << "--" << std::endl;
+
+ std::vector<node_type> actual;
+ for (const node_type& v : db.segment_range())
+ {
+ std::cout << "start=" << v.start << "; end=" << v.end << "; value='" << v.value << "'" << std::endl;
+ actual.push_back(v);
+ }
+
+ assert(expected == actual);
+
+ // Use it with structured binding
+ std::cout << "--" << std::endl;
+ actual.clear();
+ for (const auto& [start, end, value] : db.segment_range())
+ {
+ std::cout << "start=" << start << "; end=" << end << "; value='" << value << "'" << std::endl;
+ actual.emplace_back(start, end, value);
+ }
+
+ assert(expected == actual);
+ }
+}
+
+class custom_key_type
+{
+ long value;
+
+public:
+ custom_key_type() : value(0)
+ {}
+ custom_key_type(const std::string& src) : value(std::stol(src))
+ {}
+
+ bool operator==(const custom_key_type& other) const
+ {
+ return value == other.value;
+ }
+
+ bool operator!=(const custom_key_type& other) const
+ {
+ return !operator==(other);
+ }
+
+ bool operator<(const custom_key_type& other) const
+ {
+ return value < other.value;
+ }
+
+ bool operator<=(const custom_key_type& other) const
+ {
+ return value <= other.value;
+ }
+
+#if 0 // intentionally not implementing these operators
+ bool operator>(const custom_key_type& other) const
+ {
+ return value > other.value;
+ }
+
+ bool operator>=(const custom_key_type& other) const
+ {
+ return value >= other.value;
+ }
+#endif
+};
+
+void fst_test_custom_key_type()
+{
+ MDDS_TEST_FUNC_SCOPE;
+
+ using container_type = mdds::flat_segment_tree<custom_key_type, std::string>;
+ using node_type = container_type::const_segment_iterator::value_type;
+
+ container_type db(custom_key_type{"0"}, custom_key_type{"123"}, "-");
+
+ db.insert_back(custom_key_type{"10"}, custom_key_type{"45"}, "10-45");
+
+ const std::vector<node_type> expected = {
+ {custom_key_type{"0"}, custom_key_type{"10"}, "-"},
+ {custom_key_type{"10"}, custom_key_type{"45"}, "10-45"},
+ {custom_key_type{"45"}, custom_key_type{"123"}, "-"},
+ };
+
+ std::vector<node_type> actual;
+
+ for (const node_type& v : db.segment_range())
+ actual.push_back(v);
+
+ assert(expected == actual);
+}
+
+int main(int argc, char** argv)
+{
+ try
+ {
+ cmd_options opt;
+ if (!parse_cmd_options(argc, argv, opt))
+ return EXIT_FAILURE;
+
+ if (opt.test_func)
+ {
+ fst_test_equality();
+ fst_test_copy_ctor();
+ fst_test_move_ctor();
+ fst_test_back_insert();
+ {
+ typedef unsigned int key_type;
+ typedef unsigned short value_type;
+ for (value_type i = 0; i <= 100; ++i)
+ fst_test_insert_front_back<key_type, value_type>(0, 100, i);
+ }
+
+ {
+ typedef int key_type;
+ typedef short value_type;
+ for (value_type i = 0; i <= 100; ++i)
+ fst_test_insert_front_back<key_type, value_type>(0, 100, i);
+ }
+
+ {
+ typedef long key_type;
+ typedef unsigned int value_type;
+ for (value_type i = 0; i <= 100; ++i)
+ fst_test_insert_front_back<key_type, value_type>(0, 100, i);
+ }
+
+ fst_test_leaf_search();
+ fst_test_leaf_search_2();
+ fst_test_tree_build();
+ fst_test_tree_search();
+ fst_test_tree_search_2();
+ fst_test_insert_search_mix();
+ fst_test_shift_left();
+ fst_test_shift_left_right_edge();
+ fst_test_shift_left_append_new_segment();
+ fst_test_shift_right_init0();
+ fst_test_shift_right_init999();
+ fst_test_shift_right_bool();
+ fst_test_shift_right_skip_start_node();
+ fst_test_shift_right_all_nodes();
+ fst_test_const_iterator();
+ fst_test_insert_iterator();
+ fst_test_insert_state_changed();
+ fst_test_position_search();
+ fst_test_min_max_default();
+ fst_test_swap();
+ fst_test_swap_tree_memory();
+ fst_test_clear();
+ fst_test_assignment();
+ fst_test_move_assignment();
+ fst_test_non_numeric_value();
+ fst_test_insert_out_of_bound();
+ fst_test_insert_out_of_bound_2();
+ fst_test_segment_iterator();
+ fst_test_segment_range();
+ fst_test_custom_key_type();
+ }
+
+ if (opt.test_perf)
+ {
+ fst_perf_test_search_leaf();
+ fst_perf_test_search_tree();
+ fst_perf_test_insert_front_back();
+ fst_perf_test_insert_position();
+ fst_perf_test_position_search();
+ }
+ }
+ catch (const std::exception& e)
+ {
+ fprintf(stdout, "Test failed: %s\n", e.what());
+ return EXIT_FAILURE;
+ }
+
+ fprintf(stdout, "Test finished successfully!\n");
+ return 0;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 13:12:17 +0000