[mdds] 10/62: Imported Upstream version 0.5.0
This is an automated email from the git hooks/post-receive script.
rene pushed a commit to branch master
in repository mdds.
commit 5c9607fcf7c85c00c90cdf6106c102362f3eedbb
Author: Rene Engelhard <rene@debian.org>
Date: Thu Apr 21 14:50:46 2016 +0200
Imported Upstream version 0.5.0
---
Makefile.in | 32 +-
NEWS | 30 +-
VERSION.in | 1 +
bin/pack-release.sh.in | 12 -
configure | 50 +-
include/mdds/flat_segment_tree.hpp | 939 ++++++-----------------------
include/mdds/flat_segment_tree_def.inl | 686 +++++++++++++++++++++
include/mdds/flat_segment_tree_itr.hpp | 189 ++++++
include/mdds/mixed_type_matrix_element.hpp | 2 +-
include/mdds/node.hpp | 133 +++-
include/mdds/segment_tree.hpp | 131 ++--
include/{ => obsolete}/nodecontainer.hpp | 0
include/{ => obsolete}/rangetree.hpp | 0
misc/mdds.spec.in | 4 +-
src/flat_segment_tree_test.cpp | 685 +++++++++++++--------
src/mixed_type_matrix_test.cpp | 97 +--
src/rectangle_set_test.cpp | 70 +--
src/segment_tree_test.cpp | 71 +--
src/test_global.hpp | 107 ++++
19 files changed, 1883 insertions(+), 1356 deletions(-)
diff --git a/Makefile.in b/Makefile.in
index 6551284..72c493f 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -1,3 +1,6 @@
+prefix=@prefix@
+datarootdir=@datarootdir@
+PACKAGE_TARNAME=@PACKAGE_TARNAME@
OBJDIR=@OBJDIR@
SRCDIR=@SRCDIR@
@@ -18,6 +21,7 @@ HEADERS= \
$(INCDIR)/mdds/quad_node.hpp \
$(INCDIR)/mdds/global.hpp \
$(INCDIR)/mdds/flat_segment_tree.hpp \
+ $(INCDIR)/mdds/flat_segment_tree_def.inl \
$(INCDIR)/mdds/point_quad_tree.hpp \
$(INCDIR)/mdds/segment_tree.hpp \
$(INCDIR)/mdds/mixed_type_matrix.hpp \
@@ -91,10 +95,13 @@ $(OBJDIR)/template_test.o: $(SRCDIR)/template_test.cpp $(DEPENDS)
$(CXX) $(CPPFLAGS) -c -o $@ $(SRCDIR)/template_test.cpp
test.fst: flat_segment_tree_test
- ./flat_segment_tree_test
+ ./flat_segment_tree_test func
+
+test.fst.perf: flat_segment_tree_test
+ ./flat_segment_tree_test perf
test.fst.mem: flat_segment_tree_test
- valgrind --tool=memcheck --leak-check=full ./flat_segment_tree_test
+ valgrind --tool=memcheck --leak-check=full ./flat_segment_tree_test func
test.pqt: point_quad_tree_test
./point_quad_tree_test
@@ -121,7 +128,10 @@ test.st.mem: segment_tree_test
valgrind --tool=memcheck --leak-check=full ./segment_tree_test func
test.mtm: mixed_type_matrix_test
- ./mixed_type_matrix_test
+ ./mixed_type_matrix_test func
+
+test.mtm.perf: mixed_type_matrix_test
+ ./mixed_type_matrix_test perf
test.mtm.mem: mixed_type_matrix_test
valgrind --tool=memcheck --leak-check=full ./mixed_type_matrix_test func
@@ -130,15 +140,13 @@ test.stl: stlperf_test
./stlperf_test
install: $(HEADERS)
- install -d @PREFIX@/include/mdds
- install -d @PREFIX@/include/mdds/hash_container
- install -d @PREFIX@/share/mdds-devel/example
- install -d @PREFIX@/share/doc/packages/mdds-devel/
- install -m 644 -t @PREFIX@/include/mdds $(INCDIR)/mdds/*.hpp
- install -m 644 -t @PREFIX@/include/mdds $(INCDIR)/mdds/*.inl
- install -m 644 -t @PREFIX@/include/mdds/hash_container $(INCDIR)/mdds/hash_container/*.hpp
- install -m 644 -t @PREFIX@/share/mdds-devel/example/ example/*
- install -m 644 -t @PREFIX@/share/doc/packages/mdds-devel/ AUTHORS NEWS README
+ install -d $(DESTDIR)@includedir@/mdds
+ install -d $(DESTDIR)@includedir@/mdds/hash_container
+ install -d $(DESTDIR)@docdir@
+ install -m 644 -t $(DESTDIR)@includedir@/mdds $(INCDIR)/mdds/*.hpp
+ install -m 644 -t $(DESTDIR)@includedir@/mdds $(INCDIR)/mdds/*.inl
+ install -m 644 -t $(DESTDIR)@includedir@/mdds/hash_container $(INCDIR)/mdds/hash_container/*.hpp
+ install -m 644 -t $(DESTDIR)@docdir@ AUTHORS NEWS README
check: $(ALL_TESTS)
diff --git a/NEWS b/NEWS
index b5a4e33..6c7c25d 100644
--- a/NEWS
+++ b/NEWS
@@ -1,6 +1,31 @@
+mdds 0.5.0
+
+ * flat_segment_tree's search methods now return a std::pair of
+ const_iterator and bool, instead of just returning bool.
+
+ * fixed a weird enum value mis-handling with mixed_type_matrix when
+ compiled with MSVC++.
+
+ * added new insert() method to flat_segment_tree that takes a
+ positional hint to boost insertion speed. Also, all three
+ insert() methods now return the start position of the segment that
+ an inserted segment belongs to.
+
+ * slight performance improvement on the insert methods.
+
+ * slight performance improvement on the iterators of
+ flat_segment_tree.
+
+ * re-organized the structure of flat_segment_tree to split it into
+ multiple headers.
+
+ * properly support prefix, docdir, includedir configure options.
+
+ * support DESTDIR environment variable for make install.
+
mdds 0.4.0
-* implemented mixed_type_matrix.
+ * implemented mixed_type_matrix.
mdds 0.3.1
@@ -18,7 +43,8 @@ mdds 0.2.1
* fixed a bug in segment_tree::search_result object, to make it work
with empty result set.
- * fixed segment_tree to make it really usable outside of unit test code.
+ * fixed segment_tree to make it really usable outside of unit test
+ code.
mdds 0.2.0
diff --git a/VERSION.in b/VERSION.in
new file mode 100644
index 0000000..d78bda9
--- /dev/null
+++ b/VERSION.in
@@ -0,0 +1 @@
+@VERSION@
diff --git a/bin/pack-release.sh.in b/bin/pack-release.sh.in
deleted file mode 100755
index 4744f27..0000000
--- a/bin/pack-release.sh.in
+++ /dev/null
@@ -1,12 +0,0 @@
-#!/bin/bash
-
-VERSION=@VERSION@
-DIR=mdds_$VERSION
-hg clone https://multidimalgorithm.googlecode.com/hg/ $DIR
-pushd .
-cd $DIR
-autoconf
-rm -rf autom4te.cache .hg .hgtags bin autogen.sh configure.ac
-popd
-find $DIR -name '*.vp?' -type f | xargs rm -f
-tar jcvf $DIR.tar.bz2 $DIR
diff --git a/configure b/configure
index 2042821..0cd838f 100755
--- a/configure
+++ b/configure
@@ -1,6 +1,6 @@
#! /bin/sh
# Guess values for system-dependent variables and create Makefiles.
-# Generated by GNU Autoconf 2.63 for mdds 0.4.0.
+# Generated by GNU Autoconf 2.63 for mdds 0.5.0.
#
# Report bugs to <kohei.yoshida@gmail.com>.
#
@@ -596,8 +596,8 @@ SHELL=${CONFIG_SHELL-/bin/sh}
# Identity of this package.
PACKAGE_NAME='mdds'
PACKAGE_TARNAME='mdds'
-PACKAGE_VERSION='0.4.0'
-PACKAGE_STRING='mdds 0.4.0'
+PACKAGE_VERSION='0.5.0'
+PACKAGE_STRING='mdds 0.5.0'
PACKAGE_BUGREPORT='kohei.yoshida@gmail.com'
ac_subst_vars='LTLIBOBJS
@@ -606,7 +606,6 @@ CPPFLAGS
INCDIR
SRCDIR
OBJDIR
-PREFIX
VERSION
target_alias
host_alias
@@ -1205,7 +1204,7 @@ if test "$ac_init_help" = "long"; then
# Omit some internal or obsolete options to make the list less imposing.
# This message is too long to be a string in the A/UX 3.1 sh.
cat <<_ACEOF
-\`configure' configures mdds 0.4.0 to adapt to many kinds of systems.
+\`configure' configures mdds 0.5.0 to adapt to many kinds of systems.
Usage: $0 [OPTION]... [VAR=VALUE]...
@@ -1266,7 +1265,7 @@ fi
if test -n "$ac_init_help"; then
case $ac_init_help in
- short | recursive ) echo "Configuration of mdds 0.4.0:";;
+ short | recursive ) echo "Configuration of mdds 0.5.0:";;
esac
cat <<\_ACEOF
@@ -1350,7 +1349,7 @@ fi
test -n "$ac_init_help" && exit $ac_status
if $ac_init_version; then
cat <<\_ACEOF
-mdds configure 0.4.0
+mdds configure 0.5.0
generated by GNU Autoconf 2.63
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001,
@@ -1364,7 +1363,7 @@ cat >config.log <<_ACEOF
This file contains any messages produced by compilers while
running configure, to aid debugging if configure makes a mistake.
-It was created by mdds $as_me 0.4.0, which was
+It was created by mdds $as_me 0.5.0, which was
generated by GNU Autoconf 2.63. Invocation command line was
$ $0 $@
@@ -1733,7 +1732,10 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu
-VERSION=0.4.0
+VERSION=0.5.0
+
+
+PACKAGE_TARNAME=mdds
@@ -1745,16 +1747,6 @@ else
fi
-{ $as_echo "$as_me:$LINENO: checking prefix" >&5
-$as_echo_n "checking prefix... " >&6; }
-if test "$prefix" = "NONE"; then
- prefix=/usr/local
-fi
-PREFIX=$prefix
-{ $as_echo "$as_me:$LINENO: result: $prefix" >&5
-$as_echo "$prefix" >&6; }
-
-
{ $as_echo "$as_me:$LINENO: checking hash container type" >&5
$as_echo_n "checking hash container type... " >&6; }
{ $as_echo "$as_me:$LINENO: result: $with_hash_container" >&5
@@ -2236,7 +2228,7 @@ exec 6>&1
# report actual input values of CONFIG_FILES etc. instead of their
# values after options handling.
ac_log="
-This file was extended by mdds $as_me 0.4.0, which was
+This file was extended by mdds $as_me 0.5.0, which was
generated by GNU Autoconf 2.63. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -2286,7 +2278,7 @@ Report bugs to <bug-autoconf@gnu.org>."
_ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_version="\\
-mdds config.status 0.4.0
+mdds config.status 0.5.0
configured by $0, generated by GNU Autoconf 2.63,
with options \\"`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`\\"
@@ -3348,7 +3340,7 @@ exec 6>&1
# report actual input values of CONFIG_FILES etc. instead of their
# values after options handling.
ac_log="
-This file was extended by mdds $as_me 0.4.0, which was
+This file was extended by mdds $as_me 0.5.0, which was
generated by GNU Autoconf 2.63. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -3398,7 +3390,7 @@ Report bugs to <bug-autoconf@gnu.org>."
_ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_version="\\
-mdds config.status 0.4.0
+mdds config.status 0.5.0
configured by $0, generated by GNU Autoconf 2.63,
with options \\"`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`\\"
@@ -4461,7 +4453,7 @@ exec 6>&1
# report actual input values of CONFIG_FILES etc. instead of their
# values after options handling.
ac_log="
-This file was extended by mdds $as_me 0.4.0, which was
+This file was extended by mdds $as_me 0.5.0, which was
generated by GNU Autoconf 2.63. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -4511,7 +4503,7 @@ Report bugs to <bug-autoconf@gnu.org>."
_ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_version="\\
-mdds config.status 0.4.0
+mdds config.status 0.5.0
configured by $0, generated by GNU Autoconf 2.63,
with options \\"`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`\\"
@@ -5118,7 +5110,7 @@ if test -n "$ac_unrecognized_opts" && test "$enable_option_checking" != no; then
$as_echo "$as_me: WARNING: unrecognized options: $ac_unrecognized_opts" >&2;}
fi
-ac_config_files="$ac_config_files bin/pack-release.sh"
+ac_config_files="$ac_config_files VERSION"
cat >confcache <<\_ACEOF
# This file is a shell script that caches the results of configure
@@ -5575,7 +5567,7 @@ exec 6>&1
# report actual input values of CONFIG_FILES etc. instead of their
# values after options handling.
ac_log="
-This file was extended by mdds $as_me 0.4.0, which was
+This file was extended by mdds $as_me 0.5.0, which was
generated by GNU Autoconf 2.63. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -5625,7 +5617,7 @@ Report bugs to <bug-autoconf@gnu.org>."
_ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_version="\\
-mdds config.status 0.4.0
+mdds config.status 0.5.0
configured by $0, generated by GNU Autoconf 2.63,
with options \\"`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`\\"
@@ -5731,7 +5723,7 @@ do
"Makefile") CONFIG_FILES="$CONFIG_FILES Makefile" ;;
"example/Makefile") CONFIG_FILES="$CONFIG_FILES example/Makefile" ;;
"misc/mdds.spec") CONFIG_FILES="$CONFIG_FILES misc/mdds.spec" ;;
- "bin/pack-release.sh") CONFIG_FILES="$CONFIG_FILES bin/pack-release.sh" ;;
+ "VERSION") CONFIG_FILES="$CONFIG_FILES VERSION" ;;
*) { { $as_echo "$as_me:$LINENO: error: invalid argument: $ac_config_target" >&5
$as_echo "$as_me: error: invalid argument: $ac_config_target" >&2;}
diff --git a/include/mdds/flat_segment_tree.hpp b/include/mdds/flat_segment_tree.hpp
index f30403b..2db5098 100644
--- a/include/mdds/flat_segment_tree.hpp
+++ b/include/mdds/flat_segment_tree.hpp
@@ -25,15 +25,17 @@
*
************************************************************************/
-#ifndef __MDDS_FLATSEGMENTTREE_HPP__
-#define __MDDS_FLATSEGMENTTREE_HPP__
+#ifndef __MDDS_FLAT_SEGMENT_TREE_HPP__
+#define __MDDS_FLAT_SEGMENT_TREE_HPP__
#include <iostream>
+#include <sstream>
#include <utility>
#include <cassert>
#include <limits>
#include "node.hpp"
+#include "flat_segment_tree_itr.hpp"
#ifdef UNIT_TEST
#include <cstdio>
@@ -49,83 +51,44 @@ public:
typedef _Key key_type;
typedef _Value value_type;
-private:
struct nonleaf_value_type
{
key_type low; /// low range value (inclusive)
key_type high; /// high range value (non-inclusive)
+
+ bool operator== (const nonleaf_value_type& r) const
+ {
+ return low == r.low && high == r.high;
+ }
};
struct leaf_value_type
{
key_type key;
value_type value;
- };
-#ifdef UNIT_TEST
-public:
-#endif
- struct node;
- typedef ::boost::intrusive_ptr<node> node_ptr;
-
- struct node : public node_base<node_ptr, node>
- {
- union {
- nonleaf_value_type value_nonleaf;
- leaf_value_type value_leaf;
- };
-
- node(bool _is_leaf) :
- node_base<node_ptr, node>(_is_leaf)
+
+ bool operator== (const leaf_value_type& r) const
{
+ return key == r.key && value == r.value;
}
+ };
- node(const node& r) :
- node_base<node_ptr, node>(r)
- {
- if (this->is_leaf)
- {
- value_leaf.key = r.value_leaf.key;
- value_leaf.value = r.value_leaf.value;
- }
- else
- {
- value_nonleaf.low = r.value_nonleaf.low;
- value_nonleaf.high = r.value_nonleaf.high;
- }
- }
-
- void dispose()
- {
- }
-
- bool equals(const node& r) const
- {
- if (this->is_leaf != r.is_leaf)
- return false;
+ // Handlers required by the node template class.
+ struct fill_nonleaf_value_handler;
+ struct to_string_handler;
+ struct init_handler;
+ struct dispose_handler;
- if (this->is_leaf)
- {
- if (value_leaf.key != r.value_leaf.key)
- return false;
- if (value_leaf.value != r.value_leaf.value)
- return false;
- }
- else
- {
- if (value_nonleaf.low != r.value_nonleaf.low)
- return false;
- if (value_nonleaf.high != r.value_nonleaf.high)
- return false;
- }
+ typedef typename ::mdds::node<flat_segment_tree> node;
+ typedef typename node::node_ptr node_ptr;
- return true;
- }
-
- void fill_nonleaf_value(const node_ptr& left_node, const node_ptr& right_node)
+ struct fill_nonleaf_value_handler
+ {
+ void operator() (node& _self, const node_ptr& left_node, const node_ptr& right_node)
{
// Parent node should carry the range of all of its child nodes.
if (left_node)
- value_nonleaf.low = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.low;
+ _self.value_nonleaf.low = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.low;
else
// Having a left node is prerequisite.
return;
@@ -139,158 +102,86 @@ public:
// right leaf node (if such node exists).
if (right_node->right)
- value_nonleaf.high = right_node->right->value_leaf.key;
+ _self.value_nonleaf.high = right_node->right->value_leaf.key;
else
- value_nonleaf.high = right_node->value_leaf.key;
+ _self.value_nonleaf.high = right_node->value_leaf.key;
}
else
{
- value_nonleaf.high = right_node->value_nonleaf.high;
+ _self.value_nonleaf.high = right_node->value_nonleaf.high;
}
}
else
- value_nonleaf.high = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.high;
+ _self.value_nonleaf.high = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.high;
}
-
-#ifdef UNIT_TEST
- void dump_value() const
- {
- using ::std::cout;
- if (this->is_leaf)
- {
- cout << "(" << value_leaf.key << ")";
- }
- else
- {
- cout << "(" << value_nonleaf.low << "-" << value_nonleaf.high << ")";
- }
- cout << " ";
- }
-#endif
};
-private:
- class const_iterator_base
+ struct to_string_handler
{
- public:
- typedef flat_segment_tree<key_type, value_type> fst_type;
-
- explicit const_iterator_base(const fst_type* _db, bool _end, bool _forward) :
- m_db(_db), m_pos(NULL), m_end_pos(_end), m_forward(_forward)
- {
- if (!_db)
- return;
-
- if (m_forward)
- {
- // forward direction
- m_pos = _end ? _db->m_right_leaf.get() : _db->m_left_leaf.get();
- }
- else
- {
- // reverse direction
- m_pos = _end ? _db->m_left_leaf.get() : _db->m_right_leaf.get();
- }
- }
-
- const_iterator_base(const const_iterator_base& r) :
- m_db(r.m_db), m_pos(r.m_pos), m_end_pos(r.m_end_pos), m_forward(r.m_forward) {}
-
- const_iterator_base& operator=(const const_iterator_base& r)
- {
- m_db = r.m_db;
- m_pos = r.m_pos;
- return *this;
- }
-
- const ::std::pair<key_type, value_type>* operator++()
+ ::std::string operator() (const node& _self) const
{
- assert(m_pos);
- if (m_forward)
+ ::std::ostringstream os;
+ if (_self.is_leaf)
{
- if (m_pos == m_db->m_right_leaf.get())
- m_end_pos = true;
- else
- m_pos = m_pos->right.get();
+ os << "(" << _self.value_leaf.key << ")";
}
else
{
- if (m_pos == m_db->m_left_leaf.get())
- m_end_pos = true;
- else
- m_pos = m_pos->left.get();
+ os << "(" << _self.value_nonleaf.low << "-" << _self.value_nonleaf.high << ")";
}
-
- return operator->();
- }
-
- const ::std::pair<key_type, value_type>* operator--()
- {
- assert(m_pos);
- if (m_end_pos)
- m_end_pos = false;
- else
- m_pos = m_forward ? m_pos->left.get() : m_pos->right.get();
-
- return operator->();
- }
-
- bool operator==(const const_iterator_base& r) const
- {
- return (m_end_pos == r.m_end_pos) && (m_pos == r.m_pos);
- }
-
- bool operator!=(const const_iterator_base& r) const
- {
- return !operator==(r);
+ os << " ";
+ return os.str();
}
+ };
- const ::std::pair<key_type, value_type>& operator*()
- {
- return get_current_node_pair();
- }
+ struct init_handler
+ {
+ void operator() (node& /*_self*/) {}
+ };
- const ::std::pair<key_type, value_type>* operator->()
- {
- return &get_current_node_pair();
- }
+ struct dispose_handler
+ {
+ void operator() (node& /*_self*/) {}
+ };
- private:
- const ::std::pair<key_type, value_type>& get_current_node_pair()
- {
- m_current_pair = ::std::pair<key_type, value_type>(m_pos->value_leaf.key, m_pos->value_leaf.value);
- return m_current_pair;
- }
+private:
- const fst_type* m_db;
- const typename fst_type::node* m_pos;
- ::std::pair<key_type, value_type> m_current_pair;
- bool m_end_pos:1;
- bool m_forward:1;
- };
+ friend struct ::mdds::__fst::itr_forward_handler<flat_segment_tree>;
+ friend struct ::mdds::__fst::itr_reverse_handler<flat_segment_tree>;
public:
- class const_iterator : public const_iterator_base
+ class const_iterator : public ::mdds::__fst::const_iterator_base<
+ flat_segment_tree, ::mdds::__fst::itr_forward_handler<flat_segment_tree> >
{
+ typedef ::mdds::__fst::const_iterator_base<
+ flat_segment_tree, ::mdds::__fst::itr_forward_handler<flat_segment_tree> >
+ base_type;
friend class flat_segment_tree;
public:
const_iterator() :
- const_iterator_base(NULL, false, true) {}
+ base_type(NULL, false) {}
private:
- explicit const_iterator(const typename const_iterator_base::fst_type* _db, bool _end) :
- const_iterator_base(_db, _end, true) {}
+ explicit const_iterator(const typename base_type::fst_type* _db, bool _end) :
+ base_type(_db, _end) {}
+
+ explicit const_iterator(const typename base_type::fst_type* _db, const node* p) :
+ base_type(_db, p) {}
};
- class const_reverse_iterator : public const_iterator_base
+ class const_reverse_iterator : public ::mdds::__fst::const_iterator_base<
+ flat_segment_tree, ::mdds::__fst::itr_reverse_handler<flat_segment_tree> >
{
+ typedef ::mdds::__fst::const_iterator_base<
+ flat_segment_tree, ::mdds::__fst::itr_reverse_handler<flat_segment_tree> >
+ base_type;
friend class flat_segment_tree;
public:
const_reverse_iterator() :
- const_iterator_base(NULL, false, false) {}
+ base_type(NULL, false) {}
private:
- explicit const_reverse_iterator(const typename const_iterator_base::fst_type* _db, bool _end) :
- const_iterator_base(_db, _end, false) {}
+ explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) :
+ base_type(_db, _end) {}
};
const_iterator begin() const
@@ -330,23 +221,57 @@ public:
* is inclusive.
* @param end_key end value of the segment being inserted. The value is
* not inclusive.
- * @param val value associated with this segment.
+ * @param val value associated with this segment.
+ *
+ * @return pair of const_iterator corresponding to the start position of
+ * the inserted segment, and a boolean value indicating whether or
+ * not the insertion has been successful.
*/
- void insert_front(key_type start_key, key_type end_key, value_type val)
+ ::std::pair<const_iterator, bool>
+ insert_front(key_type start_key, key_type end_key, value_type val)
{
- insert_segment_impl(start_key, end_key, val, true);
+ return insert_segment_impl(start_key, end_key, val, true);
}
/**
* Insert a new segment into the tree. Unlike
* the <code>insert_front</code>, this method searches for the point of
* insertion from the last leaf node toward the first.
+ *
+ * @param start_key start value of the segment being inserted. The value
+ * is inclusive.
+ * @param end_key end value of the segment being inserted. The value is
+ * not inclusive.
+ * @param val value associated with this segment.
+ *
+ * @return pair of const_iterator corresponding to the start position of
+ * the inserted segment, and a boolean value indicating whether or
+ * not the insertion has been successful.
*/
- void insert_back(key_type start_key, key_type end_key, value_type val)
+ ::std::pair<const_iterator, bool>
+ insert_back(key_type start_key, key_type end_key, value_type val)
{
- insert_segment_impl(start_key, end_key, val, false);
+ return insert_segment_impl(start_key, end_key, val, false);
}
+ /**
+ * Insert a new segment into the tree at or after specified point of
+ * insertion.
+ *
+ * @param pos specified insertion point
+ * @param start_key start value of the segment being inserted. The value
+ * is inclusive.
+ * @param end_key end value of the segment being inserted. The value is
+ * not inclusive.
+ * @param val value associated with this segment.
+ *
+ * @return pair of const_iterator corresponding to the start position of
+ * the inserted segment, and a boolean value indicating whether or
+ * not the insertion has been successful.
+ */
+ ::std::pair<const_iterator, bool>
+ insert(const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
+
/**
* Remove a segment specified by the start and end key values, and shift
* the remaining segments (i.e. those segments that come after the removed
@@ -372,8 +297,65 @@ public:
*/
void shift_right(key_type pos, key_type size, bool skip_start_node);
- bool search(key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const;
-
+ /**
+ * Perform leaf-node search for a value associated with a key.
+ *
+ * @param key key value
+ * @param value value associated with key specified gets stored upon
+ * successful search.
+ * @param start_key pointer to a variable where the start key value of the
+ * segment that contains the key gets stored upon
+ * successful search.
+ * @param end_key pointer to a varaible where the end key value of the
+ * segment that contains the key gets stored upon
+ * successful search.
+ * @return a pair of const_iterator corresponding to the start position of
+ * the segment containing the key, and a boolean value indicating
+ * whether or not the search has been successful.
+ *
+ */
+ ::std::pair<const_iterator, bool>
+ search(key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const;
+
+ /**
+ * Perform leaf-node search for a value associated with a key.
+ *
+ * @param pos position from which the search should start. When the
+ * position is invalid, it falls back to the normal search.
+ * @param key key value
+ * @param value value associated with key specified gets stored upon
+ * successful search.
+ * @param start_key pointer to a variable where the start key value of the
+ * segment that contains the key gets stored upon
+ * successful search.
+ * @param end_key pointer to a varaible where the end key value of the
+ * segment that contains the key gets stored upon
+ * successful search.
+ * @return a pair of const_iterator corresponding to the start position of
+ * the segment containing the key, and a boolean value indicating
+ * whether or not the search has been successful.
+ *
+ */
+ ::std::pair<const_iterator, bool>
+ search(const const_iterator& pos, key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const;
+
+ /**
+ * Perform tree search for a value associated with a key. This method
+ * assumes that the tree is valid.
+ *
+ * @param key key value
+ * @param value value associated with key specified gets stored upon
+ * successful search.
+ * @param start_key pointer to a variable where the start key value of the
+ * segment that contains the key gets stored upon
+ * successful search.
+ * @param end_key pointer to a varaible where the end key value of the
+ * segment that contains the key gets stored upon
+ * successful search.
+ * @return a boolean value indicating whether or not the search has been
+ * successful.
+ *
+ */
bool search_tree(key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const;
void build_tree();
@@ -410,7 +392,7 @@ public:
assert(!"attempted to dump an invalid tree!");
size_t node_count = ::mdds::dump_tree(m_root_node);
- size_t node_instance_count = node_base<node_ptr, node>::get_instance_count();
+ size_t node_instance_count = node::get_instance_count();
cout << "tree node count = " << node_count << " node instance count = " << node_instance_count << endl;
assert(node_count == node_instance_count);
@@ -432,7 +414,7 @@ public:
<< endl;
cur_node = cur_node->right;
}
- cout << endl << " node instance count = " << node_base<node_ptr, node>::get_instance_count() << endl;
+ cout << endl << " node instance count = " << node::get_instance_count() << endl;
}
/**
@@ -532,10 +514,16 @@ private:
m_valid_tree = false;
}
- void insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward);
+ ::std::pair<const_iterator, bool>
+ insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward);
+
+ ::std::pair<const_iterator, bool>
+ insert_to_pos(node_ptr& start_pos, key_type start_key, key_type end_key, value_type val);
+
+ ::std::pair<const_iterator, bool>
+ search_impl(const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
- node_ptr get_insertion_pos_leaf(key_type key, const node_ptr& start_pos) const;
- node_ptr get_insertion_pos_leaf_reverse(key_type key, const node_ptr& start_pos) const;
+ const node* get_insertion_pos_leaf_reverse(key_type key, const node* start_pos) const;
const node* get_insertion_pos_leaf(key_type key, const node* start_pos) const;
@@ -584,579 +572,12 @@ private:
node_ptr m_root_node;
node_ptr m_left_leaf;
node_ptr m_right_leaf;
- value_type m_init_val;
- bool m_valid_tree;
+ value_type m_init_val;
+ bool m_valid_tree;
};
-template<typename _Key, typename _Value>
-flat_segment_tree<_Key, _Value>::flat_segment_tree(key_type min_val, key_type max_val, value_type init_val) :
- m_root_node(static_cast<node*>(NULL)),
- m_left_leaf(new node(true)),
- m_right_leaf(new node(true)),
- m_init_val(init_val),
- m_valid_tree(false)
-{
- // we need to create two end nodes during initialization.
- m_left_leaf->value_leaf.key = min_val;
- m_left_leaf->value_leaf.value = init_val;
- m_left_leaf->right = m_right_leaf;
-
- m_right_leaf->value_leaf.key = max_val;
- m_right_leaf->left = m_left_leaf;
-
- // We don't ever use the value of the right leaf node, but we need the
- // value to be always the same, to make it easier to check for
- // equality.
- m_right_leaf->value_leaf.value = ::std::numeric_limits<value_type>::max();
-}
-
-template<typename _Key, typename _Value>
-flat_segment_tree<_Key, _Value>::flat_segment_tree(const flat_segment_tree<_Key, _Value>& r) :
- m_root_node(static_cast<node*>(NULL)),
- m_left_leaf(new node(static_cast<const node&>(*r.m_left_leaf))),
- m_right_leaf(static_cast<node*>(NULL)),
- m_init_val(r.m_init_val),
- m_valid_tree(false) // tree is invalid because we only copy the leaf nodes.
-{
- // Copy all the leaf nodes from the original instance.
- node* src_node = r.m_left_leaf.get();
- node_ptr dest_node = m_left_leaf;
- while (true)
- {
- dest_node->right.reset(new node(*src_node->right));
-
- // Move on to the next source node.
- src_node = src_node->right.get();
-
- // Move on to the next destination node, and have the next node point
- // back to the previous node.
- node_ptr old_node = dest_node;
- dest_node = dest_node->right;
- dest_node->left = old_node;
-
- if (src_node == r.m_right_leaf.get())
- {
- // Reached the right most leaf node. We can stop here.
- m_right_leaf = dest_node;
- break;
- }
- }
-}
-
-template<typename _Key, typename _Value>
-flat_segment_tree<_Key, _Value>::~flat_segment_tree()
-{
- disconnect_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
- clear_tree(m_root_node.get());
- disconnect_all_nodes(m_root_node.get());
-}
-
-template<typename _Key, typename _Value>
-void flat_segment_tree<_Key, _Value>::insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward)
-{
- if (end_key < m_left_leaf->value_leaf.key || start_key > m_right_leaf->value_leaf.key)
- // The new segment does not overlap the current interval.
- return;
-
- if (start_key < m_left_leaf->value_leaf.key)
- // The start value should not be smaller than the current minimum.
- start_key = m_left_leaf->value_leaf.key;
-
- if (end_key > m_right_leaf->value_leaf.key)
- // The end value should not be larger than the current maximum.
- end_key = m_right_leaf->value_leaf.key;
-
- if (start_key >= end_key)
- return;
-
- // Find the node with value that either equals or is greater than the
- // start value.
-
- node_ptr start_pos;
- if (forward)
- {
- start_pos = get_insertion_pos_leaf(start_key, m_left_leaf);
- }
- else
- {
- start_pos = get_insertion_pos_leaf_reverse(start_key, m_right_leaf);
- if (start_pos)
- start_pos = start_pos->right;
- else
- start_pos = m_left_leaf;
- }
- if (!start_pos)
- {
- // Insertion position not found. Bail out.
- assert(!"Insertion position not found. Bail out");
- return;
- }
-
-
- node_ptr end_pos = get_insertion_pos_leaf(end_key, start_pos);
- if (!end_pos)
- end_pos = m_right_leaf;
-
- node_ptr new_start_node;
- value_type old_value;
-
- // Set the start node.
-
- if (start_pos->value_leaf.key == start_key)
- {
- // Re-use the existing node, but save the old value for later.
-
- if (start_pos->left && start_pos->left->value_leaf.value == val)
- {
- // Extend the existing segment.
- old_value = start_pos->value_leaf.value;
- new_start_node = start_pos->left;
- }
- else
- {
- // Update the value of the existing node.
- old_value = start_pos->value_leaf.value;
- start_pos->value_leaf.value = val;
- new_start_node = start_pos;
- }
- }
- else if (start_pos->left->value_leaf.value == val)
- {
- // Extend the existing segment.
- old_value = start_pos->left->value_leaf.value;
- new_start_node = start_pos->left;
- }
- else
- {
- // Insert a new node before the insertion position node.
- node_ptr new_node(new node(true));
- new_node->value_leaf.key = start_key;
- new_node->value_leaf.value = val;
- new_start_node = new_node;
-
- node_ptr left_node = start_pos->left;
- old_value = left_node->value_leaf.value;
-
- // Link to the left node.
- link_nodes(left_node, new_node);
-
- // Link to the right node.
- link_nodes(new_node, start_pos);
- }
-
- node_ptr cur_node = new_start_node->right;
- while (cur_node != end_pos)
- {
- // Disconnect the link between the current node and the previous node.
- cur_node->left->right.reset();
- cur_node->left.reset();
- old_value = cur_node->value_leaf.value;
-
- cur_node = cur_node->right;
- }
-
- // Set the end node.
-
- if (end_pos->value_leaf.key == end_key)
- {
- // The new segment ends exactly at the end node position.
-
- if (end_pos->right && end_pos->value_leaf.value == val)
- {
- // Remove this node, and connect the new start node with the
- // node that comes after this node.
- new_start_node->right = end_pos->right;
- if (end_pos->right)
- end_pos->right->left = new_start_node;
- disconnect_all_nodes(end_pos.get());
- }
- else
- {
- // Just link the new segment to this node.
- new_start_node->right = end_pos;
- end_pos->left = new_start_node;
- }
- }
- else if (old_value == val)
- {
- link_nodes(new_start_node, end_pos);
- }
- else
- {
- // Insert a new node before the insertion position node.
- node_ptr new_node(new node(true));
- new_node->value_leaf.key = end_key;
- new_node->value_leaf.value = old_value;
-
- // Link to the left node.
- link_nodes(new_start_node, new_node);
-
- // Link to the right node.
- link_nodes(new_node, end_pos);
- }
-
- m_valid_tree = false;
-}
-
-template<typename _Key, typename _Value>
-void flat_segment_tree<_Key, _Value>::shift_left(key_type start_key, key_type end_key)
-{
- if (start_key >= end_key)
- return;
-
- key_type left_leaf_key = m_left_leaf->value_leaf.key;
- key_type right_leaf_key = m_right_leaf->value_leaf.key;
- if (start_key < left_leaf_key || end_key < left_leaf_key)
- // invalid key value
- return;
-
- if (start_key > right_leaf_key || end_key > right_leaf_key)
- // invalid key value.
- return;
-
- node_ptr node_pos;
- if (left_leaf_key == start_key)
- node_pos = m_left_leaf;
- else
- // Get the first node with a key value equal to or greater than the
- // start key value. But we want to skip the leftmost node.
- node_pos = get_insertion_pos_leaf(start_key, m_left_leaf->right);
-
- if (!node_pos)
- return;
-
- key_type segment_size = end_key - start_key;
-
- if (node_pos == m_right_leaf)
- {
- // The segment being removed begins after the last node before the
- // right-most node.
-
- if (right_leaf_key <= end_key)
- {
- // The end position equals or is past the right-most node.
- append_new_segment(start_key);
- }
- else
- {
- // The end position stops before the right-most node. Simply
- // append the blank segment to the end.
- append_new_segment(right_leaf_key - segment_size);
- }
- return;
- }
-
- if (end_key < node_pos->value_leaf.key)
- {
- // The removed segment does not overlap with any nodes. Simply
- // shift the key values of those nodes that come after the removed
- // segment.
- shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
- append_new_segment(right_leaf_key - segment_size);
- m_valid_tree = false;
- return;
- }
-
- // Move the first node to the starting position, and from there search
- // for the first node whose key value is greater than the end value.
- node_pos->value_leaf.key = start_key;
- node_ptr start_pos = node_pos;
- node_pos = node_pos->right;
- value_type last_seg_value = start_pos->value_leaf.value;
- while (node_pos.get() != m_right_leaf.get() && node_pos->value_leaf.key <= end_key)
- {
- last_seg_value = node_pos->value_leaf.value;
- node_ptr next = node_pos->right;
- disconnect_all_nodes(node_pos.get());
- node_pos = next;
- }
-
- start_pos->value_leaf.value = last_seg_value;
- start_pos->right = node_pos;
- node_pos->left = start_pos;
- if (start_pos->left && start_pos->left->value_leaf.value == start_pos->value_leaf.value)
- {
- // Removing a segment resulted in two consecutive segments with
- // identical value. Combine them by removing the 2nd redundant
- // node.
- start_pos->left->right = start_pos->right;
- start_pos->right->left = start_pos->left;
- disconnect_all_nodes(start_pos.get());
- }
-
- shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
- m_valid_tree = false;
-
- // Insert at the end a new segment with the initial base value, for
- // the length of the removed segment.
- append_new_segment(right_leaf_key - segment_size);
-}
-
-template<typename _Key, typename _Value>
-void flat_segment_tree<_Key, _Value>::shift_right(key_type pos, key_type size, bool skip_start_node)
-{
- if (size <= 0)
- return;
-
- if (pos < m_left_leaf->value_leaf.key || m_right_leaf->value_leaf.key <= pos)
- // specified position is out-of-bound
- return;
-
- if (m_left_leaf->value_leaf.key == pos)
- {
- // Position is at the leftmost node. Shift all the other nodes,
- // and insert a new node at (pos + size) position.
- node_ptr cur_node = m_left_leaf->right;
- shift_leaf_key_right(cur_node, m_right_leaf, size);
-
- if (m_left_leaf->value_leaf.value != m_init_val)
- {
- // The leftmost leaf node has a non-initial value. We need to
- // insert a new node to carry that value after the shift.
- node_ptr new_node(new node(true));
- new_node->value_leaf.key = pos + size;
- new_node->value_leaf.value = m_left_leaf->value_leaf.value;
- m_left_leaf->value_leaf.value = m_init_val;
- new_node->left = m_left_leaf;
- new_node->right = m_left_leaf->right;
- m_left_leaf->right = new_node;
- }
-
- m_valid_tree = false;
- return;
- }
-
- // Get the first node with a key value equal to or greater than the
- // start key value. But we want to skip the leftmost node.
- node_ptr cur_node = get_insertion_pos_leaf(pos, m_left_leaf->right);
-
- // If the point of insertion is at an existing node position, don't
- // shift that node but start with the one after it if that's
- // requested.
- if (skip_start_node && cur_node && cur_node->value_leaf.key == pos)
- cur_node = cur_node->right;
-
- if (!cur_node)
- return;
-
- shift_leaf_key_right(cur_node, m_right_leaf, size);
- m_valid_tree = false;
-}
-
-template<typename _Key, typename _Value>
-bool flat_segment_tree<_Key, _Value>::search(
- key_type key, value_type& value, key_type* start_key, key_type* end_key) const
-{
- if (key < m_left_leaf->value_leaf.key || m_right_leaf->value_leaf.key <= key)
- // key value is out-of-bound.
- return false;
-
- const node* pos = get_insertion_pos_leaf(key, m_left_leaf.get());
- if (pos->value_leaf.key == key)
- {
- value = pos->value_leaf.value;
- if (start_key)
- *start_key = pos->value_leaf.key;
- if (end_key && pos->right)
- *end_key = pos->right->value_leaf.key;
- return true;
- }
- else if (pos->left && pos->left->value_leaf.key < key)
- {
- value = pos->left->value_leaf.value;
- if (start_key)
- *start_key = pos->left->value_leaf.key;
- if (end_key)
- *end_key = pos->value_leaf.key;
- return true;
- }
-
- return false;
-}
-
-template<typename _Key, typename _Value>
-bool flat_segment_tree<_Key, _Value>::search_tree(
- key_type key, value_type& value, key_type* start_key, key_type* end_key) const
-{
- if (!m_root_node || !m_valid_tree)
- {
- // either tree has not been built, or is in an invalid state.
- return false;
- }
-
- if (key < m_left_leaf->value_leaf.key || m_right_leaf->value_leaf.key <= key)
- {
- // key value is out-of-bound.
- return false;
- }
-
- // Descend down the tree through the last non-leaf layer.
-
- node* cur_node = m_root_node.get();
- while (true)
- {
- if (cur_node->left)
- {
- if (cur_node->left->is_leaf)
- break;
-
- const nonleaf_value_type& v = cur_node->left->value_nonleaf;
- if (v.low <= key && key < v.high)
- {
- cur_node = cur_node->left.get();
- continue;
- }
- }
- else
- {
- // left child node can't be missing !
- return false;
- }
-
- if (cur_node->right)
- {
- const nonleaf_value_type& v = cur_node->right->value_nonleaf;
- if (v.low <= key && key < v.high)
- {
- cur_node = cur_node->right.get();
- continue;
- }
- }
- return false;
- }
-
- assert(cur_node->left->is_leaf && cur_node->right->is_leaf);
-
- key_type key1 = cur_node->left->value_leaf.key;
- key_type key2 = cur_node->right->value_leaf.key;
-
- if (key1 <= key && key < key2)
- {
- cur_node = cur_node->left.get();
- }
- else if (key2 <= key && key < cur_node->value_nonleaf.high)
- {
- cur_node = cur_node->right.get();
- }
- else
- cur_node = NULL;
-
- if (!cur_node)
- {
- return false;
- }
-
- value = cur_node->value_leaf.value;
- if (start_key)
- *start_key = cur_node->value_leaf.key;
-
- if (end_key)
- {
- assert(cur_node->right);
- if (cur_node->right)
- *end_key = cur_node->right->value_leaf.key;
- else
- // This should never happen, but just in case....
- *end_key = m_right_leaf->value_leaf.key;
- }
-
- return true;
-}
-
-template<typename _Key, typename _Value>
-void flat_segment_tree<_Key, _Value>::build_tree()
-{
- if (!m_left_leaf)
- return;
-
- clear_tree(m_root_node.get());
- m_root_node = ::mdds::build_tree<node_ptr, node>(m_left_leaf);
- m_valid_tree = true;
-}
-
-template<typename _Key, typename _Value>
-bool flat_segment_tree<_Key, _Value>::operator==(const flat_segment_tree<key_type, value_type>& r) const
-{
- const node* n1 = m_left_leaf.get();
- const node* n2 = r.m_left_leaf.get();
-
- if ((!n1 && n2) || (n1 && !n2))
- // Either one of them is NULL;
- return false;
-
- while (n1)
- {
- if (!n2)
- return false;
-
- if (!n1->equals(*n2))
- return false;
-
- n1 = n1->right.get();
- n2 = n2->right.get();
- }
-
- if (n2)
- // n1 is NULL, but n2 is not.
- return false;
-
- // All leaf nodes are equal.
- return true;
-}
-
-template<typename _Key, typename _Value>
-typename flat_segment_tree<_Key, _Value>::node_ptr
-flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf(
- key_type key, const node_ptr& start_pos) const
-{
- node_ptr cur_node = start_pos;
- while (cur_node)
- {
- if (key <= cur_node->value_leaf.key)
- {
- // Found the insertion position.
- return cur_node;
- }
- cur_node = cur_node->right;
- }
- return node_ptr();
-}
-
-template<typename _Key, typename _Value>
-typename flat_segment_tree<_Key, _Value>::node_ptr
-flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf_reverse(
- key_type key, const node_ptr& start_pos) const
-{
- node_ptr cur_node = start_pos;
- while (cur_node)
- {
- if (key > cur_node->value_leaf.key)
- {
- // Found the insertion position.
- return cur_node;
- }
- cur_node = cur_node->left;
- }
- return node_ptr();
-}
-
-template<typename _Key, typename _Value>
-const typename flat_segment_tree<_Key, _Value>::node*
-flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf(key_type key, const node* start_pos) const
-{
- const node* cur_node = start_pos;
- while (cur_node)
- {
- if (key <= cur_node->value_leaf.key)
- {
- // Found the insertion position.
- return cur_node;
- }
- cur_node = cur_node->right.get();
- }
- return NULL;
-}
-
} // namespace mdds
+#include "flat_segment_tree_def.inl"
+
#endif
diff --git a/include/mdds/flat_segment_tree_def.inl b/include/mdds/flat_segment_tree_def.inl
new file mode 100644
index 0000000..086663b
--- /dev/null
+++ b/include/mdds/flat_segment_tree_def.inl
@@ -0,0 +1,686 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2010 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.
+ *
+ ************************************************************************/
+
+namespace mdds {
+
+template<typename _Key, typename _Value>
+flat_segment_tree<_Key, _Value>::flat_segment_tree(key_type min_val, key_type max_val, value_type init_val) :
+ m_root_node(static_cast<node*>(NULL)),
+ m_left_leaf(new node(true)),
+ m_right_leaf(new node(true)),
+ m_init_val(init_val),
+ m_valid_tree(false)
+{
+ // we need to create two end nodes during initialization.
+ m_left_leaf->value_leaf.key = min_val;
+ m_left_leaf->value_leaf.value = init_val;
+ m_left_leaf->right = m_right_leaf;
+
+ m_right_leaf->value_leaf.key = max_val;
+ m_right_leaf->left = m_left_leaf;
+
+ // We don't ever use the value of the right leaf node, but we need the
+ // value to be always the same, to make it easier to check for
+ // equality.
+ m_right_leaf->value_leaf.value = ::std::numeric_limits<value_type>::max();
+}
+
+template<typename _Key, typename _Value>
+flat_segment_tree<_Key, _Value>::flat_segment_tree(const flat_segment_tree<_Key, _Value>& r) :
+ m_root_node(static_cast<node*>(NULL)),
+ m_left_leaf(new node(static_cast<const node&>(*r.m_left_leaf))),
+ m_right_leaf(static_cast<node*>(NULL)),
+ m_init_val(r.m_init_val),
+ m_valid_tree(false) // tree is invalid because we only copy the leaf nodes.
+{
+ // Copy all the leaf nodes from the original instance.
+ node* src_node = r.m_left_leaf.get();
+ node_ptr dest_node = m_left_leaf;
+ while (true)
+ {
+ dest_node->right.reset(new node(*src_node->right));
+
+ // Move on to the next source node.
+ src_node = src_node->right.get();
+
+ // Move on to the next destination node, and have the next node point
+ // back to the previous node.
+ node_ptr old_node = dest_node;
+ dest_node = dest_node->right;
+ dest_node->left = old_node;
+
+ if (src_node == r.m_right_leaf.get())
+ {
+ // Reached the right most leaf node. We can stop here.
+ m_right_leaf = dest_node;
+ break;
+ }
+ }
+}
+
+template<typename _Key, typename _Value>
+flat_segment_tree<_Key, _Value>::~flat_segment_tree()
+{
+ disconnect_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
+ clear_tree(m_root_node.get());
+ disconnect_all_nodes(m_root_node.get());
+}
+
+template<typename _Key, typename _Value>
+::std::pair<typename flat_segment_tree<_Key, _Value>::const_iterator, bool>
+flat_segment_tree<_Key, _Value>::insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward)
+{
+ typedef ::std::pair<typename flat_segment_tree<_Key, _Value>::const_iterator, bool> ret_type;
+
+ if (end_key < m_left_leaf->value_leaf.key || start_key > m_right_leaf->value_leaf.key)
+ // The new segment does not overlap the current interval.
+ return ret_type(const_iterator(this, true), false);
+
+ if (start_key < m_left_leaf->value_leaf.key)
+ // The start value should not be smaller than the current minimum.
+ start_key = m_left_leaf->value_leaf.key;
+
+ if (end_key > m_right_leaf->value_leaf.key)
+ // The end value should not be larger than the current maximum.
+ end_key = m_right_leaf->value_leaf.key;
+
+ if (start_key >= end_key)
+ return ret_type(const_iterator(this, true), false);
+
+ // Find the node with value that either equals or is greater than the
+ // start value.
+
+ node_ptr start_pos;
+ if (forward)
+ {
+ const node* p = get_insertion_pos_leaf(start_key, m_left_leaf.get());
+ start_pos.reset(const_cast<node*>(p));
+ }
+ else
+ {
+ const node* p = get_insertion_pos_leaf_reverse(start_key, m_right_leaf.get());
+ if (p)
+ start_pos = p->right;
+ else
+ start_pos = m_left_leaf;
+ }
+ if (!start_pos)
+ {
+ // Insertion position not found. Bail out.
+ assert(!"Insertion position not found. Bail out");
+ return ret_type(const_iterator(this, true), false);
+ }
+
+ return insert_to_pos(start_pos, start_key, end_key, val);
+}
+
+template<typename _Key, typename _Value>
+::std::pair<typename flat_segment_tree<_Key, _Value>::const_iterator, bool>
+flat_segment_tree<_Key, _Value>::insert_to_pos(
+ node_ptr& start_pos, key_type start_key, key_type end_key, value_type val)
+{
+ node_ptr end_pos;
+ {
+ const node* p = get_insertion_pos_leaf(end_key, start_pos.get());
+ end_pos.reset(const_cast<node*>(p));
+ }
+ if (!end_pos)
+ end_pos = m_right_leaf;
+
+ node_ptr new_start_node;
+ value_type old_value;
+
+ // Set the start node.
+
+ bool changed = false;
+
+ if (start_pos->value_leaf.key == start_key)
+ {
+ // Re-use the existing node, but save the old value for later.
+
+ if (start_pos->left && start_pos->left->value_leaf.value == val)
+ {
+ // Extend the existing segment.
+ old_value = start_pos->value_leaf.value;
+ new_start_node = start_pos->left;
+ }
+ else
+ {
+ // Update the value of the existing node.
+ old_value = start_pos->value_leaf.value;
+ start_pos->value_leaf.value = val;
+ new_start_node = start_pos;
+
+ changed = (old_value != val);
+ }
+ }
+ else if (start_pos->left->value_leaf.value == val)
+ {
+ // Extend the existing segment.
+ old_value = start_pos->left->value_leaf.value;
+ new_start_node = start_pos->left;
+ }
+ else
+ {
+ // Insert a new node before the insertion position node.
+ node_ptr new_node(new node(true));
+ new_node->value_leaf.key = start_key;
+ new_node->value_leaf.value = val;
+ new_start_node = new_node;
+
+ node_ptr left_node = start_pos->left;
+ old_value = left_node->value_leaf.value;
+
+ // Link to the left node.
+ link_nodes(left_node, new_node);
+
+ // Link to the right node.
+ link_nodes(new_node, start_pos);
+ changed = true;
+ }
+
+ node_ptr cur_node = new_start_node->right;
+ while (cur_node != end_pos)
+ {
+ // Disconnect the link between the current node and the previous node.
+ cur_node->left->right.reset();
+ cur_node->left.reset();
+ old_value = cur_node->value_leaf.value;
+
+ cur_node = cur_node->right;
+ changed = true;
+ }
+
+ // Set the end node.
+
+ if (end_pos->value_leaf.key == end_key)
+ {
+ // The new segment ends exactly at the end node position.
+
+ if (end_pos->right && end_pos->value_leaf.value == val)
+ {
+ // Remove this node, and connect the new start node with the
+ // node that comes after this node.
+ new_start_node->right = end_pos->right;
+ if (end_pos->right)
+ end_pos->right->left = new_start_node;
+ disconnect_all_nodes(end_pos.get());
+ changed = true;
+ }
+ else if (new_start_node->right != end_pos)
+ {
+ // Just link the new segment to this node.
+ new_start_node->right = end_pos;
+ end_pos->left = new_start_node;
+ changed = true;
+ }
+ }
+ else if (old_value == val)
+ {
+ if (new_start_node->right != end_pos)
+ {
+ link_nodes(new_start_node, end_pos);
+ changed = true;
+ }
+ }
+ else
+ {
+ // Insert a new node before the insertion position node.
+ node_ptr new_node(new node(true));
+ new_node->value_leaf.key = end_key;
+ new_node->value_leaf.value = old_value;
+
+ // Link to the left node.
+ link_nodes(new_start_node, new_node);
+
+ // Link to the right node.
+ link_nodes(new_node, end_pos);
+ changed = true;
+ }
+
+ if (changed)
+ m_valid_tree = false;
+
+ return ::std::pair<const_iterator, bool>(
+ const_iterator(this, new_start_node.get()), changed);
+}
+
+template<typename _Key, typename _Value>
+::std::pair<typename flat_segment_tree<_Key, _Value>::const_iterator, bool>
+flat_segment_tree<_Key, _Value>::insert(
+ const const_iterator& pos, key_type start_key, key_type end_key, value_type val)
+{
+ const node* p = pos.get_pos();
+ if (!p || this != pos.get_parent())
+ {
+ // Switch to normal insert.
+ return insert_front(start_key, end_key, val);
+ }
+
+ assert(p->is_leaf);
+
+ if (start_key < p->value_leaf.key)
+ {
+ // Specified position is already past the start key position. Not good.
+ return insert_front(start_key, end_key, val);
+ }
+
+ p = get_insertion_pos_leaf(start_key, p);
+ node_ptr start_pos(const_cast<node*>(p));
+ return insert_to_pos(start_pos, start_key, end_key, val);
+}
+
+template<typename _Key, typename _Value>
+void flat_segment_tree<_Key, _Value>::shift_left(key_type start_key, key_type end_key)
+{
+ if (start_key >= end_key)
+ return;
+
+ key_type left_leaf_key = m_left_leaf->value_leaf.key;
+ key_type right_leaf_key = m_right_leaf->value_leaf.key;
+ if (start_key < left_leaf_key || end_key < left_leaf_key)
+ // invalid key value
+ return;
+
+ if (start_key > right_leaf_key || end_key > right_leaf_key)
+ // invalid key value.
+ return;
+
+ node_ptr node_pos;
+ if (left_leaf_key == start_key)
+ node_pos = m_left_leaf;
+ else
+ {
+ // Get the first node with a key value equal to or greater than the
+ // start key value. But we want to skip the leftmost node.
+ const node* p = get_insertion_pos_leaf(start_key, m_left_leaf->right.get());
+ node_pos.reset(const_cast<node*>(p));
+ }
+
+ if (!node_pos)
+ return;
+
+ key_type segment_size = end_key - start_key;
+
+ if (node_pos == m_right_leaf)
+ {
+ // The segment being removed begins after the last node before the
+ // right-most node.
+
+ if (right_leaf_key <= end_key)
+ {
+ // The end position equals or is past the right-most node.
+ append_new_segment(start_key);
+ }
+ else
+ {
+ // The end position stops before the right-most node. Simply
+ // append the blank segment to the end.
+ append_new_segment(right_leaf_key - segment_size);
+ }
+ return;
+ }
+
+ if (end_key < node_pos->value_leaf.key)
+ {
+ // The removed segment does not overlap with any nodes. Simply
+ // shift the key values of those nodes that come after the removed
+ // segment.
+ shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
+ append_new_segment(right_leaf_key - segment_size);
+ m_valid_tree = false;
+ return;
+ }
+
+ // Move the first node to the starting position, and from there search
+ // for the first node whose key value is greater than the end value.
+ node_pos->value_leaf.key = start_key;
+ node_ptr start_pos = node_pos;
+ node_pos = node_pos->right;
+ value_type last_seg_value = start_pos->value_leaf.value;
+ while (node_pos.get() != m_right_leaf.get() && node_pos->value_leaf.key <= end_key)
+ {
+ last_seg_value = node_pos->value_leaf.value;
+ node_ptr next = node_pos->right;
+ disconnect_all_nodes(node_pos.get());
+ node_pos = next;
+ }
+
+ start_pos->value_leaf.value = last_seg_value;
+ start_pos->right = node_pos;
+ node_pos->left = start_pos;
+ if (start_pos->left && start_pos->left->value_leaf.value == start_pos->value_leaf.value)
+ {
+ // Removing a segment resulted in two consecutive segments with
+ // identical value. Combine them by removing the 2nd redundant
+ // node.
+ start_pos->left->right = start_pos->right;
+ start_pos->right->left = start_pos->left;
+ disconnect_all_nodes(start_pos.get());
+ }
+
+ shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
+ m_valid_tree = false;
+
+ // Insert at the end a new segment with the initial base value, for
+ // the length of the removed segment.
+ append_new_segment(right_leaf_key - segment_size);
+}
+
+template<typename _Key, typename _Value>
+void flat_segment_tree<_Key, _Value>::shift_right(key_type pos, key_type size, bool skip_start_node)
+{
+ if (size <= 0)
+ return;
+
+ if (pos < m_left_leaf->value_leaf.key || m_right_leaf->value_leaf.key <= pos)
+ // specified position is out-of-bound
+ return;
+
+ if (m_left_leaf->value_leaf.key == pos)
+ {
+ // Position is at the leftmost node. Shift all the other nodes,
+ // and insert a new node at (pos + size) position.
+ node_ptr cur_node = m_left_leaf->right;
+ shift_leaf_key_right(cur_node, m_right_leaf, size);
+
+ if (m_left_leaf->value_leaf.value != m_init_val)
+ {
+ // The leftmost leaf node has a non-initial value. We need to
+ // insert a new node to carry that value after the shift.
+ node_ptr new_node(new node(true));
+ new_node->value_leaf.key = pos + size;
+ new_node->value_leaf.value = m_left_leaf->value_leaf.value;
+ m_left_leaf->value_leaf.value = m_init_val;
+ new_node->left = m_left_leaf;
+ new_node->right = m_left_leaf->right;
+ m_left_leaf->right = new_node;
+ }
+
+ m_valid_tree = false;
+ return;
+ }
+
+ // Get the first node with a key value equal to or greater than the
+ // start key value. But we want to skip the leftmost node.
+ const node* p = get_insertion_pos_leaf(pos, m_left_leaf->right.get());
+ node_ptr cur_node(const_cast<node*>(p));
+
+ // If the point of insertion is at an existing node position, don't
+ // shift that node but start with the one after it if that's
+ // requested.
+ if (skip_start_node && cur_node && cur_node->value_leaf.key == pos)
+ cur_node = cur_node->right;
+
+ if (!cur_node)
+ return;
+
+ shift_leaf_key_right(cur_node, m_right_leaf, size);
+ m_valid_tree = false;
+}
+
+template<typename _Key, typename _Value>
+::std::pair<typename flat_segment_tree<_Key, _Value>::const_iterator, bool>
+flat_segment_tree<_Key, _Value>::search_impl(const node* pos,
+ key_type key, value_type& value, key_type* start_key, key_type* end_key) const
+{
+ typedef ::std::pair<const_iterator, bool> ret_type;
+
+ if (pos->value_leaf.key == key)
+ {
+ value = pos->value_leaf.value;
+ if (start_key)
+ *start_key = pos->value_leaf.key;
+ if (end_key && pos->right)
+ *end_key = pos->right->value_leaf.key;
+ return ret_type(const_iterator(this, pos), true);
+ }
+ else if (pos->left && pos->left->value_leaf.key < key)
+ {
+ value = pos->left->value_leaf.value;
+ if (start_key)
+ *start_key = pos->left->value_leaf.key;
+ if (end_key)
+ *end_key = pos->value_leaf.key;
+ return ret_type(const_iterator(this, pos->left.get()), true);
+ }
+
+ return ret_type(const_iterator(this, true), false);
+}
+
+template<typename _Key, typename _Value>
+::std::pair<typename flat_segment_tree<_Key, _Value>::const_iterator, bool>
+flat_segment_tree<_Key, _Value>::search(
+ key_type key, value_type& value, key_type* start_key, key_type* end_key) const
+{
+ typedef ::std::pair<const_iterator, bool> ret_type;
+
+ if (key < m_left_leaf->value_leaf.key || m_right_leaf->value_leaf.key <= key)
+ // key value is out-of-bound.
+ return ret_type(const_iterator(this, true), false);
+
+ const node* pos = get_insertion_pos_leaf(key, m_left_leaf.get());
+ return search_impl(pos, key, value, start_key, end_key);
+}
+
+template<typename _Key, typename _Value>
+::std::pair<typename flat_segment_tree<_Key, _Value>::const_iterator, bool>
+flat_segment_tree<_Key, _Value>::search(const const_iterator& pos,
+ key_type key, value_type& value, key_type* start_key, key_type* end_key) const
+{
+ typedef ::std::pair<const_iterator, bool> ret_type;
+
+ if (key < m_left_leaf->value_leaf.key || m_right_leaf->value_leaf.key <= key)
+ // key value is out-of-bound.
+ return ret_type(const_iterator(this, true), false);
+
+ const node* p = pos.get_pos();
+ if (!p || this != pos.get_parent())
+ {
+ // Switch to normal search.
+ return search(key, value, start_key, end_key);
+ }
+
+ assert(p->is_leaf);
+
+ if (key < p->value_leaf.key)
+ {
+ // Specified position is already past the start key position. Fall
+ // back to normal search.
+ return search(key, value, start_key, end_key);
+ }
+
+ p = get_insertion_pos_leaf(key, p);
+ return search_impl(p, key, value, start_key, end_key);
+}
+
+template<typename _Key, typename _Value>
+bool flat_segment_tree<_Key, _Value>::search_tree(
+ key_type key, value_type& value, key_type* start_key, key_type* end_key) const
+{
+ if (!m_root_node || !m_valid_tree)
+ {
+ // either tree has not been built, or is in an invalid state.
+ return false;
+ }
+
+ if (key < m_left_leaf->value_leaf.key || m_right_leaf->value_leaf.key <= key)
+ {
+ // key value is out-of-bound.
+ return false;
+ }
+
+ // Descend down the tree through the last non-leaf layer.
+
+ node* cur_node = m_root_node.get();
+ while (true)
+ {
+ if (cur_node->left)
+ {
+ if (cur_node->left->is_leaf)
+ break;
+
+ const nonleaf_value_type& v = cur_node->left->value_nonleaf;
+ if (v.low <= key && key < v.high)
+ {
+ cur_node = cur_node->left.get();
+ continue;
+ }
+ }
+ else
+ {
+ // left child node can't be missing !
+ return false;
+ }
+
+ if (cur_node->right)
+ {
+ const nonleaf_value_type& v = cur_node->right->value_nonleaf;
+ if (v.low <= key && key < v.high)
+ {
+ cur_node = cur_node->right.get();
+ continue;
+ }
+ }
+ return false;
+ }
+
+ assert(cur_node->left->is_leaf && cur_node->right->is_leaf);
+
+ key_type key1 = cur_node->left->value_leaf.key;
+ key_type key2 = cur_node->right->value_leaf.key;
+
+ if (key1 <= key && key < key2)
+ {
+ cur_node = cur_node->left.get();
+ }
+ else if (key2 <= key && key < cur_node->value_nonleaf.high)
+ {
+ cur_node = cur_node->right.get();
+ }
+ else
+ cur_node = NULL;
+
+ if (!cur_node)
+ {
+ return false;
+ }
+
+ value = cur_node->value_leaf.value;
+ if (start_key)
+ *start_key = cur_node->value_leaf.key;
+
+ if (end_key)
+ {
+ assert(cur_node->right);
+ if (cur_node->right)
+ *end_key = cur_node->right->value_leaf.key;
+ else
+ // This should never happen, but just in case....
+ *end_key = m_right_leaf->value_leaf.key;
+ }
+
+ return true;
+}
+
+template<typename _Key, typename _Value>
+void flat_segment_tree<_Key, _Value>::build_tree()
+{
+ if (!m_left_leaf)
+ return;
+
+ clear_tree(m_root_node.get());
+ m_root_node = ::mdds::build_tree<node_ptr, node>(m_left_leaf);
+ m_valid_tree = true;
+}
+
+template<typename _Key, typename _Value>
+bool flat_segment_tree<_Key, _Value>::operator==(const flat_segment_tree<key_type, value_type>& r) const
+{
+ const node* n1 = m_left_leaf.get();
+ const node* n2 = r.m_left_leaf.get();
+
+ if ((!n1 && n2) || (n1 && !n2))
+ // Either one of them is NULL;
+ return false;
+
+ while (n1)
+ {
+ if (!n2)
+ return false;
+
+ if (!n1->equals(*n2))
+ return false;
+
+ n1 = n1->right.get();
+ n2 = n2->right.get();
+ }
+
+ if (n2)
+ // n1 is NULL, but n2 is not.
+ return false;
+
+ // All leaf nodes are equal.
+ return true;
+}
+
+template<typename _Key, typename _Value>
+const typename flat_segment_tree<_Key, _Value>::node*
+flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf_reverse(
+ key_type key, const node* start_pos) const
+{
+ const node* cur_node = start_pos;
+ while (cur_node)
+ {
+ if (key > cur_node->value_leaf.key)
+ {
+ // Found the insertion position.
+ return cur_node;
+ }
+ cur_node = cur_node->left.get();
+ }
+ return NULL;
+}
+
+template<typename _Key, typename _Value>
+const typename flat_segment_tree<_Key, _Value>::node*
+flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf(key_type key, const node* start_pos) const
+{
+ const node* cur_node = start_pos;
+ while (cur_node)
+ {
+ if (key <= cur_node->value_leaf.key)
+ {
+ // Found the insertion position.
+ return cur_node;
+ }
+ cur_node = cur_node->right.get();
+ }
+ return NULL;
+}
+
+}
diff --git a/include/mdds/flat_segment_tree_itr.hpp b/include/mdds/flat_segment_tree_itr.hpp
new file mode 100644
index 0000000..b307d69
--- /dev/null
+++ b/include/mdds/flat_segment_tree_itr.hpp
@@ -0,0 +1,189 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2010 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#ifndef __MDDS_FLAT_SEGMENT_TREE_ITR_HPP__
+#define __MDDS_FLAT_SEGMENT_TREE_ITR_HPP__
+
+namespace mdds { namespace __fst {
+
+/**
+ * Handler for forward iterator
+ */
+template<typename _FstType>
+struct itr_forward_handler
+{
+ typedef _FstType fst_type;
+
+ const typename fst_type::node* init_pos(const fst_type* _db, bool _end) const
+ {
+ return _end ? _db->m_right_leaf.get() : _db->m_left_leaf.get();
+ }
+
+ void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end) const
+ {
+ if (p == _db->m_right_leaf.get())
+ end = true;
+ else
+ p = p->right.get();
+ }
+
+ void dec(const typename fst_type::node*& p, bool& end) const
+ {
+ if (end)
+ end = false;
+ else
+ p = p->left.get();
+ }
+};
+
+/**
+ * Handler for reverse iterator
+ */
+template<typename _FstType>
+struct itr_reverse_handler
+{
+ typedef _FstType fst_type;
+
+ const typename fst_type::node* init_pos(const fst_type* _db, bool _end) const
+ {
+ return _end ? _db->m_left_leaf.get() : _db->m_right_leaf.get();
+ }
+
+ void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end) const
+ {
+ if (p == _db->m_left_leaf.get())
+ end = true;
+ else
+ p = p->left.get();
+ }
+
+ void dec(const typename fst_type::node*& p, bool& end) const
+ {
+ if (end)
+ end = false;
+ else
+ p = p->right.get();
+ }
+};
+
+template<typename _FstType, typename _Hdl>
+class const_iterator_base
+{
+public:
+ typedef _FstType fst_type;
+ typedef _Hdl handler_type;
+
+ // iterator traits
+ typedef ::std::pair<typename fst_type::key_type, typename fst_type::value_type> value_type;
+ typedef value_type* pointer;
+ typedef value_type& reference;
+ typedef ptrdiff_t difference_type;
+ typedef ::std::bidirectional_iterator_tag iterator_category;
+
+ explicit const_iterator_base(const fst_type* _db, bool _end) :
+ m_db(_db), m_pos(NULL), m_end_pos(_end)
+ {
+ if (!_db)
+ return;
+
+ m_pos = m_hdl.init_pos(_db, _end);
+ }
+
+ explicit const_iterator_base(const fst_type* _db, const typename fst_type::node* pos) :
+ m_db(_db), m_pos(pos), m_end_pos(false) {}
+
+ const_iterator_base(const const_iterator_base& r) :
+ m_db(r.m_db), m_pos(r.m_pos), m_end_pos(r.m_end_pos) {}
+
+ const_iterator_base& operator=(const const_iterator_base& r)
+ {
+ m_db = r.m_db;
+ m_pos = r.m_pos;
+ return *this;
+ }
+
+ const value_type* operator++()
+ {
+ assert(m_pos);
+ m_hdl.inc(m_db, m_pos, m_end_pos);
+ return operator->();
+ }
+
+ const value_type* operator--()
+ {
+ assert(m_pos);
+ m_hdl.dec(m_pos, m_end_pos);
+ return operator->();
+ }
+
+ bool operator==(const const_iterator_base& r) const
+ {
+ if (m_db != r.m_db)
+ return false;
+
+ if (m_end_pos == r.m_end_pos)
+ return true;
+
+ return (m_pos == r.m_pos);
+ }
+
+ bool operator!=(const const_iterator_base& r) const
+ {
+ return !operator==(r);
+ }
+
+ const value_type& operator*()
+ {
+ return get_current_node_pair();
+ }
+
+ const value_type* operator->()
+ {
+ return &get_current_node_pair();
+ }
+
+protected:
+ const typename fst_type::node* get_pos() const { return m_pos; }
+ const fst_type* get_parent() const { return m_db; }
+
+private:
+ const value_type& get_current_node_pair()
+ {
+ m_current_pair = value_type(m_pos->value_leaf.key, m_pos->value_leaf.value);
+ return m_current_pair;
+ }
+
+ handler_type m_hdl;
+ const fst_type* m_db;
+ const typename fst_type::node* m_pos;
+ value_type m_current_pair;
+ bool m_end_pos;
+};
+
+}}
+
+#endif
diff --git a/include/mdds/mixed_type_matrix_element.hpp b/include/mdds/mixed_type_matrix_element.hpp
index 18eac72..e8c159b 100644
--- a/include/mdds/mixed_type_matrix_element.hpp
+++ b/include/mdds/mixed_type_matrix_element.hpp
@@ -43,7 +43,7 @@ struct element
{
typedef _String string_type;
- matrix_element_t m_type:2;
+ matrix_element_t m_type;
union
{
diff --git a/include/mdds/node.hpp b/include/mdds/node.hpp
index 3391432..876fe9a 100644
--- a/include/mdds/node.hpp
+++ b/include/mdds/node.hpp
@@ -40,9 +40,29 @@ namespace mdds {
size_t node_instance_count = 0;
#endif
-template<typename _NodePtr, typename _NodeType>
-struct node_base
+template<typename T>
+struct node_traits
{
+ typedef typename T::nonleaf_value_type nonleaf_value_type;
+ typedef typename T::leaf_value_type leaf_value_type;
+ typedef typename T::fill_nonleaf_value_handler fill_nonleaf_value_handler;
+ typedef typename T::to_string_handler to_string_handler;
+ typedef typename T::init_handler init_handler;
+ typedef typename T::dispose_handler dispose_handler;
+};
+
+template<typename T>
+struct node
+{
+ typedef ::boost::intrusive_ptr<node> node_ptr;
+
+ typedef typename node_traits<T>::nonleaf_value_type nonleaf_value_type;
+ typedef typename node_traits<T>::leaf_value_type leaf_value_type;
+ typedef typename node_traits<T>::fill_nonleaf_value_handler fill_nonleaf_value_handler;
+ typedef typename node_traits<T>::to_string_handler to_string_handler;
+ typedef typename node_traits<T>::init_handler init_handler;
+ typedef typename node_traits<T>::dispose_handler dispose_handler;
+
static size_t get_instance_count()
{
#ifdef DEBUG_NODE_BASE
@@ -51,73 +71,130 @@ struct node_base
return 0;
#endif
}
- size_t refcount;
- _NodePtr parent; /// parent node
- _NodePtr left; /// left child node or previous sibling if it's a leaf node.
- _NodePtr right; /// right child node or next sibling if it's aleaf node.
- bool is_leaf;
+ union {
+ nonleaf_value_type value_nonleaf;
+ leaf_value_type value_leaf;
+ };
+
+
+ node_ptr parent; /// parent node
+ node_ptr left; /// left child node or previous sibling if it's a leaf node.
+ node_ptr right; /// right child node or next sibling if it's aleaf node.
+ bool is_leaf;
+
+ size_t refcount;
+private:
+ fill_nonleaf_value_handler _hdl_fill_nonleaf;
+ to_string_handler _hdl_to_string;
+ init_handler _hdl_init;
+ dispose_handler _hdl_dispose;
- node_base(bool _is_leaf) :
- refcount(0),
- is_leaf(_is_leaf)
+public:
+ node(bool _is_leaf) :
+ is_leaf(_is_leaf),
+ refcount(0)
{
#ifdef DEBUG_NODE_BASE
++node_instance_count;
#endif
+ _hdl_init(*this);
}
/**
* When copying node, only the stored values should be copied.
* Connections to the parent, left and right nodes must not be copied.
*/
- node_base(const node_base& r) :
- refcount(0),
- is_leaf(r.is_leaf)
+ node(const node& r) :
+ is_leaf(r.is_leaf),
+ refcount(0)
{
#ifdef DEBUG_NODE_BASE
++node_instance_count;
#endif
+ if (is_leaf)
+ value_leaf = r.value_leaf;
+ else
+ value_nonleaf = r.value_nonleaf;
}
/**
* Like the copy constructor, only the stored values should be copied.
*/
- node_base& operator=(const node_base& r)
+ node& operator=(const node& r)
{
if (this == &r)
// assignment to self.
return *this;
is_leaf = r.is_leaf;
+ if (is_leaf)
+ value_leaf = r.value_leaf;
+ else
+ value_nonleaf = r.value_nonleaf;
return *this;
}
- ~node_base()
+ ~node()
{
#ifdef DEBUG_NODE_BASE
--node_instance_count;
#endif
- static_cast<_NodeType*>(this)->dispose();
+ dispose();
+ }
+
+ void dispose()
+ {
+ _hdl_dispose(*this);
+ }
+
+ bool equals(const node& r) const
+ {
+ if (is_leaf != r.is_leaf)
+ return false;
+
+ if (is_leaf)
+ return value_leaf == value_leaf;
+ else
+ return value_nonleaf == value_nonleaf;
+
+ return true;
}
+
+ void fill_nonleaf_value(const node_ptr& left_node, const node_ptr& right_node)
+ {
+ _hdl_fill_nonleaf(*this, left_node, right_node);
+ }
+
+#ifdef UNIT_TEST
+ void dump_value() const
+ {
+ ::std::cout << _hdl_to_string(*this);
+ }
+
+ ::std::string to_string() const
+ {
+ return _hdl_to_string(*this);
+ }
+#endif
};
-template<typename _NodePtr>
-inline void intrusive_ptr_add_ref(_NodePtr p)
+template<typename T>
+inline void intrusive_ptr_add_ref(::mdds::node<T>* p)
{
++p->refcount;
}
-template<typename _NodePtr>
-inline void intrusive_ptr_release(_NodePtr p)
+template<typename T>
+inline void intrusive_ptr_release(::mdds::node<T>* p)
{
--p->refcount;
if (!p->refcount)
delete p;
}
-template<typename _NodePtr>
-void disconnect_all_nodes(_NodePtr p)
+template<typename T>
+void disconnect_all_nodes(::mdds::node<T>* p)
{
if (!p)
return;
@@ -127,17 +204,17 @@ void disconnect_all_nodes(_NodePtr p)
p->parent.reset();
}
-template<typename _NodePtr>
-void disconnect_leaf_nodes(_NodePtr left_node, _NodePtr right_node)
+template<typename T>
+void disconnect_leaf_nodes(::mdds::node<T>* left_node, ::mdds::node<T>* right_node)
{
if (!left_node || !right_node)
return;
// Go through all leaf nodes, and disconnect their links.
- _NodePtr cur_node = left_node;
+ ::mdds::node<T>* cur_node = left_node;
do
{
- _NodePtr next_node = cur_node->right.get();
+ ::mdds::node<T>* next_node = cur_node->right.get();
disconnect_all_nodes(cur_node);
cur_node = next_node;
}
@@ -157,8 +234,8 @@ void link_nodes(_NodePtr& left, _NodePtr& right)
* Disconnect all non-leaf nodes so that their ref-counted instances will
* all get destroyed afterwards.
*/
-template<typename _NodePtr>
-void clear_tree(_NodePtr node)
+template<typename T>
+void clear_tree(::mdds::node<T>* node)
{
if (!node)
// Nothing to do.
diff --git a/include/mdds/segment_tree.hpp b/include/mdds/segment_tree.hpp
index 9c07739..22dbf82 100644
--- a/include/mdds/segment_tree.hpp
+++ b/include/mdds/segment_tree.hpp
@@ -170,59 +170,39 @@ private:
key_type low; /// low range value (inclusive)
key_type high; /// high range value (non-inclusive)
data_chain_type* data_chain;
+
+ bool operator== (const nonleaf_value_type& r) const
+ {
+ return low == r.low && high == r.high && data_chain == r.data_chain;
+ }
};
struct leaf_value_type
{
key_type key;
data_chain_type* data_chain;
- };
-
- struct node;
- typedef ::boost::intrusive_ptr<node> node_ptr;
-
- struct node : public node_base<node_ptr, node>
- {
- union {
- nonleaf_value_type value_nonleaf;
- leaf_value_type value_leaf;
- };
-
- node(bool _is_leaf) :
- node_base<node_ptr, node>(_is_leaf)
- {
- if (_is_leaf)
- value_leaf.data_chain = NULL;
- else
- value_nonleaf.data_chain = NULL;
- }
- node(const node& r) :
- node_base<node_ptr, node>(r)
+ bool operator== (const leaf_value_type& r) const
{
+ return key == r.key && data_chain == r.data_chain;
}
+ };
- void dispose()
- {
- if (this->is_leaf)
- delete value_leaf.data_chain;
- else
- delete value_nonleaf.data_chain;
- }
-
- bool equals(const node& r) const
- {
- if (this->is_leaf != r.is_leaf)
- return false;
+ struct fill_nonleaf_value_handler;
+ struct to_string_handler;
+ struct init_handler;
+ struct dispose_handler;
- return true;
- }
+ typedef ::mdds::node<segment_tree> node;
+ typedef typename node::node_ptr node_ptr;
- void fill_nonleaf_value(const node_ptr& left_node, const node_ptr& right_node)
+ struct fill_nonleaf_value_handler
+ {
+ void operator() (node& _self, const node_ptr& left_node, const node_ptr& right_node)
{
// Parent node should carry the range of all of its child nodes.
if (left_node)
- value_nonleaf.low = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.low;
+ _self.value_nonleaf.low = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.low;
else
// Having a left node is prerequisite.
return;
@@ -236,39 +216,39 @@ private:
// right leaf node (if such node exists).
if (right_node->right)
- value_nonleaf.high = right_node->right->value_leaf.key;
+ _self.value_nonleaf.high = right_node->right->value_leaf.key;
else
- value_nonleaf.high = right_node->value_leaf.key;
+ _self.value_nonleaf.high = right_node->value_leaf.key;
}
else
{
- value_nonleaf.high = right_node->value_nonleaf.high;
+ _self.value_nonleaf.high = right_node->value_nonleaf.high;
}
}
else
- value_nonleaf.high = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.high;
- }
-
-#ifdef UNIT_TEST
- void dump_value() const
- {
- ::std::cout << print();
+ _self.value_nonleaf.high = left_node->is_leaf ? left_node->value_leaf.key : left_node->value_nonleaf.high;
}
+ };
- ::std::string print() const
+ struct to_string_handler
+ {
+ ::std::string operator() (const node& _self) const
{
::std::ostringstream os;
- if (this->is_leaf)
+ if (_self.is_leaf)
{
- os << "[" << value_leaf.key << "]";
+ os << "[" << _self.value_leaf.key << "]";
}
else
{
- os << "[" << value_nonleaf.low << "-" << value_nonleaf.high << ")";
- if (value_nonleaf.data_chain)
+ os << "[" << _self.value_nonleaf.low << "-" << _self.value_nonleaf.high << ")";
+ if (_self.value_nonleaf.data_chain)
{
os << " { ";
- typename data_chain_type::const_iterator itr, itr_beg = value_nonleaf.data_chain->begin(), itr_end = value_nonleaf.data_chain->end();
+ typename data_chain_type::const_iterator
+ itr,
+ itr_beg = _self.value_nonleaf.data_chain->begin(),
+ itr_end = _self.value_nonleaf.data_chain->end();
for (itr = itr_beg; itr != itr_end; ++itr)
{
if (itr != itr_beg)
@@ -281,17 +261,40 @@ private:
os << " ";
return os.str();
}
+ };
- struct printer : public ::std::unary_function<const node*, void>
+ struct init_handler
+ {
+ void operator() (node& _self)
{
- void operator() (const node* p) const
- {
- ::std::cout << p->print() << " ";
- }
- };
-#endif
+ if (_self.is_leaf)
+ _self.value_leaf.data_chain = NULL;
+ else
+ _self.value_nonleaf.data_chain = NULL;
+ }
};
+ struct dispose_handler
+ {
+ void operator() (node& _self)
+ {
+ if (_self.is_leaf)
+ delete _self.value_leaf.data_chain;
+ else
+ delete _self.value_nonleaf.data_chain;
+ }
+ };
+
+#if UNIT_TEST
+ struct node_printer : public ::std::unary_function<const node*, void>
+ {
+ void operator() (const node* p) const
+ {
+ ::std::cout << p->to_string() << " ";
+ }
+ };
+#endif
+
private:
/**
@@ -1057,7 +1060,7 @@ void segment_tree<_Key, _Data>::dump_tree() const
cout << "dump tree ------------------------------------------------------" << endl;
size_t node_count = ::mdds::dump_tree<node_ptr>(m_root_node.get());
- size_t node_instance_count = node_base<node_ptr, node>::get_instance_count();
+ size_t node_instance_count = node::get_instance_count();
cout << "tree node count = " << node_count << " node instance count = " << node_instance_count << endl;
}
@@ -1076,7 +1079,7 @@ void segment_tree<_Key, _Data>::dump_leaf_nodes() const
print_leaf_value(p->value_leaf);
p = p->right.get();
}
- cout << " node instance count = " << node_base<node_ptr, node>::get_instance_count() << endl;
+ cout << " node instance count = " << node::get_instance_count() << endl;
}
template<typename _Key, typename _Data>
@@ -1102,7 +1105,7 @@ bool segment_tree<_Key, _Data>::verify_node_lists() const
cout << "node list " << itr->first->name << ": ";
const node_list_type* plist = itr->second;
assert(plist);
- typename node::printer func;
+ node_printer func;
for_each(plist->begin(), plist->end(), func);
cout << endl;
diff --git a/include/nodecontainer.hpp b/include/obsolete/nodecontainer.hpp
similarity index 100%
rename from include/nodecontainer.hpp
rename to include/obsolete/nodecontainer.hpp
diff --git a/include/rangetree.hpp b/include/obsolete/rangetree.hpp
similarity index 100%
rename from include/rangetree.hpp
rename to include/obsolete/rangetree.hpp
diff --git a/misc/mdds.spec.in b/misc/mdds.spec.in
index 449adf8..a9889c9 100644
--- a/misc/mdds.spec.in
+++ b/misc/mdds.spec.in
@@ -40,7 +40,7 @@ Authors:
%setup -q -n %{name}_%{version}
%build
-./configure --prefix=%buildroot/usr
+./configure --prefix=%buildroot/usr --docdir=%buildroot%{_docdir}
%check
#make check
@@ -54,9 +54,7 @@ rm -rf %buildroot
%files devel
%defattr(-,root,root)
%dir %{_docdir}
-%dir %{_datadir}/mdds-devel
%{_includedir}/mdds
-%{_datadir}/mdds-devel/example
%doc %{_docdir}/*
%changelog
diff --git a/src/flat_segment_tree_test.cpp b/src/flat_segment_tree_test.cpp
index ebad5b7..c481e1d 100644
--- a/src/flat_segment_tree_test.cpp
+++ b/src/flat_segment_tree_test.cpp
@@ -25,10 +25,8 @@
*
************************************************************************/
-#if 0 // Disabled until I re-write priority search tree in a template.
-#include "rangetree.hpp"
-#endif
#include "mdds/flat_segment_tree.hpp"
+#include "test_global.hpp"
#include <list>
#include <iostream>
@@ -42,49 +40,6 @@
using namespace std;
using namespace mdds;
-
-#include <stdio.h>
-#include <string>
-#include <sys/time.h>
-
-namespace {
-
-class StackPrinter
-{
-public:
- explicit StackPrinter(const char* msg) :
- msMsg(msg)
- {
- fprintf(stdout, "%s: --begin\n", msMsg.c_str());
- mfStartTime = getTime();
- }
-
- ~StackPrinter()
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime));
- }
-
- void printTime(int line) const
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime));
- }
-
-private:
- double getTime() const
- {
- timeval tv;
- gettimeofday(&tv, NULL);
- return tv.tv_sec + tv.tv_usec / 1000000.0;
- }
-
- ::std::string msMsg;
- double mfStartTime;
-};
-
-}
-
void printTitle(const char* msg)
{
cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
@@ -92,157 +47,6 @@ void printTitle(const char* msg)
cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
}
-#if 0 // Disabled until I re-write priority search tree in a template.
-void testPrioSearchTree()
-{
- RangeTree emptyDB;
- emptyDB.insertPoint("Raleigh", 90, 34);
- emptyDB.build();
-// emptyDB.dump();
- emptyDB.search(0, 100);
- emptyDB.search(10, 20);
-
- RangeTree rangeDB;
- rangeDB.insertPoint("North Pole", -35, -42);
- rangeDB.insertPoint("Chicago", 35, 42);
- rangeDB.insertPoint("Mobile", 52, 10);
- rangeDB.insertPoint("Toronto", 62, 77);
- rangeDB.insertPoint("Buffalo", 82, 65);
- rangeDB.insertPoint("Denver", 5, 45);
- rangeDB.insertPoint("Provo", 5, 46);
- rangeDB.insertPoint("Provo", 5, 46);
- rangeDB.insertPoint("Provo", 5, 46);
- rangeDB.insertPoint("Provo", 5, 46);
- rangeDB.insertPoint("Omaha", 27, 35);
- rangeDB.insertPoint("Atlanta", 85, 15);
- rangeDB.insertPoint("Miami", 90, 5);
- rangeDB.insertPoint("Raleigh", 90, 34);
- rangeDB.insertPoint("New York", 102, 44);
- rangeDB.insertPoint("Seattle", 2, 1029);
- rangeDB.insertPoint("Bemidji", 23, 113);
- rangeDB.build();
-// rangeDB.dump();
-
- rangeDB.search(30, 200);
- rangeDB.printSearchResult();
- rangeDB.search(0, 52);
- rangeDB.printSearchResult();
- rangeDB.search(102, 150);
- rangeDB.printSearchResult();
-
- rangeDB.search(0, 100, 30);
- rangeDB.printSearchResult();
- rangeDB.search(0, 50, 100);
- rangeDB.printSearchResult();
- rangeDB.search(40, 100, 10);
- rangeDB.printSearchResult();
- rangeDB.search(-100, 10000, -100);
- rangeDB.printSearchResult();
- rangeDB.search(-100, -99, 1000);
- rangeDB.printSearchResult();
-}
-
-void testPrioSearchTree2()
-{
- RangeTree db;
- for (int x = 0; x < 10; ++x)
- for (int y = 0; y < 10; ++y)
- db.insertPoint("point", x, y);
- db.build();
-
- for (int x = 0; x < 4; ++x)
- {
- db.search(x, x+1, 0);
- db.printSearchResult();
- }
-
- for (int x = 0; x < 4; ++x)
- for (int y = 0; y < 5; ++y)
- {
- db.search(x, x+1, y);
- db.printSearchResult();
- }
-}
-
-namespace {
-
-struct SegmentName : public segment_tree::segment_data_type
-{
- string name;
- SegmentName(const char* _name) :
- name(_name) {}
-
- virtual ~SegmentName() {}
-
- virtual size_t hash() const
- {
- size_t n = name.size();
- if (n > 10)
- // Put a cap at 10 characters.
- n = 10;
-
- size_t hash = 0;
- for (size_t i = 0; i < n; ++i)
- {
- char c = name[i];
- hash += static_cast<size_t>(c);
- }
- return hash;
- }
-
- virtual const char* what() const
- {
- return name.c_str();
- }
-};
-
-}
-
-void testSegmentTree1()
-{
- struct {
- segment_tree::value_type low;
- segment_tree::value_type high;
- SegmentName* name;
- } points[] = {
- { 6, 36, new SegmentName("A")},
- {34, 38, new SegmentName("B")},
- {21, 36, new SegmentName("C")},
- {23, 27, new SegmentName("D")},
- { 3, 8, new SegmentName("E")},
- {15, 19, new SegmentName("F")},
- {11, 14, new SegmentName("G")}
- };
-
- segment_tree db;
- size_t n = sizeof(points)/sizeof(points[0]);
- for (size_t i = 0; i < n; ++i)
- {
- cout << "inserting segment into tree: " << points[i].low << " - " << points[i].high << " ("
- << points[i].name->what() << ")" << endl;
- db.insert_front(points[i].low, points[i].high, points[i].name);
- }
-
- db.build();
- for (size_t i = 0; i < 40; ++i)
- {
- list<const segment_tree::segment_data_type*> hits;
- db.search(i, hits);
- cout << "segments that contains point " << i << ":";
- for (list<const segment_tree::segment_data_type*>::const_iterator itr = hits.begin(), itrEnd = hits.end();
- itr != itrEnd; ++itr)
- {
- const segment_tree::segment_data_type* p = *itr;
- cout << " " << static_cast<const SegmentName*>(p)->name;
- }
- cout << endl;
- }
-
- for (size_t i = 0; i < n; ++i)
- delete points[i].name;
-}
-#endif
-
void fst_test_leaf_search()
{
{
@@ -312,7 +116,7 @@ void fst_test_leaf_search()
for (int i = 0; i <= 100; ++i)
{
int val = 0;
- if (db.search(i, val))
+ if (db.search(i, val).second)
cout << "key = " << i << "; value = " << val << endl;
else
cout << "key = " << i << "; (value not found)" << endl;
@@ -320,7 +124,7 @@ void fst_test_leaf_search()
for (int i = 0; i <= 100; ++i)
{
int val = 0, start, end;
- if (db.search(i, val, &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;
@@ -396,7 +200,7 @@ void fst_perf_test_search(bool tree_search)
}
else
{
- if (db.search(i, val))
+ if (db.search(i, val).second)
++success;
else
++failure;
@@ -1186,6 +990,7 @@ 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)
{
typedef flat_segment_tree<key_type, value_type> container_type;
+ typedef typename container_type::const_iterator itr_type;
value_type val = 0;
@@ -1193,7 +998,9 @@ void fst_test_insert_front_back(key_type start_key, key_type end_key, value_type
container_type db_front(start_key, end_key, default_value);
for (key_type i = start_key; i < end_key - 10; ++i)
{
- db_front.insert_front(i, i+1, val);
+ 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;
}
@@ -1203,7 +1010,9 @@ void fst_test_insert_front_back(key_type start_key, key_type end_key, value_type
val = 0;
for (key_type i = start_key; i < end_key - 10; ++i)
{
- db_back.insert_back(i, i+1, val);
+ 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;
}
@@ -1219,7 +1028,7 @@ void fst_test_insert_front_back(key_type start_key, key_type end_key, value_type
}
}
-void fst_perf_test_insert()
+void fst_perf_test_insert_front_back()
{
typedef unsigned long key_type;
typedef int value_type;
@@ -1441,56 +1250,428 @@ void fst_test_back_insert()
db.dump_leaf_nodes();
}
-int main (int argc, char *argv[])
+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()
+{
+ StackPrinter __stack_printer__("::fst_test_insert_iterator");
+ 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()
+{
+ StackPrinter __stack_printer__("::fst_test_insert_state_changed");
+ typedef long key_type;
+ typedef short value_type;
+ typedef flat_segment_tree<key_type, value_type> db_type;
+ typedef 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()
+{
+ typedef flat_segment_tree<long, bool> db_type;
+ typedef pair<db_type::const_iterator, bool> ret_type;
+ long upper = 60000;
+ {
+ StackPrinter __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;
+ }
+ }
+
+ {
+ StackPrinter __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);
+ {
+ StackPrinter __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;
+ }
+ }
+ {
+ StackPrinter __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()
+{
+ typedef flat_segment_tree<long, bool> db_type;
+ typedef 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;
+ }
+
+ {
+ StackPrinter __stack_printer__("::fst_perf_test_position_search (normal)");
+ for (long i = 0; i < upper; ++i)
+ {
+ bool val;
+ ret_type ret = db.search(i, val);
+ assert(ret.second);
+ }
+ }
+
+ {
+ StackPrinter __stack_printer__("::fst_perf_test_position_search (positioned)");
+ itr = db.begin();
+ for (long i = 0; i < upper; ++i)
+ {
+ bool val;
+ ret_type ret = db.search(itr, i, val);
+ 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 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()
{
-#if 0 // Disabled until I re-write priority search tree in a template.
- testPrioSearchTree();
- testPrioSearchTree2();
- testSegmentTree1();
-#endif
-
- // ------------------------------------------------------------------------
- // flat_segment_tree test
-
-// fst_perf_test_insert();
- fst_test_equality();
- fst_test_copy_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_tree_build();
- fst_test_tree_search();
-// fst_perf_test_search(false);
- fst_perf_test_search(true);
- fst_test_insert_search_mix();
- fst_test_shift_segment_left();
- fst_test_shift_segment_left_right_edge();
- fst_test_shift_segment_left_append_new_segment();
- fst_test_shift_segment_right_init0();
- fst_test_shift_segment_right_init999();
- fst_test_shift_segment_right_bool();
- fst_test_shift_segment_right_skip_start_node();
- fst_test_const_iterator();
+ StackPrinter __stack_printer__("::fst_test_position_search");
+ typedef flat_segment_tree<long, short> db_type;
+ typedef 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 = sizeof(params) / sizeof(params[0]);
+
+ 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;
+ }
+}
+
+int main (int argc, char **argv)
+{
+ 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_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_tree_build();
+ fst_test_tree_search();
+ fst_test_insert_search_mix();
+ fst_test_shift_segment_left();
+ fst_test_shift_segment_left_right_edge();
+ fst_test_shift_segment_left_append_new_segment();
+ fst_test_shift_segment_right_init0();
+ fst_test_shift_segment_right_init999();
+ fst_test_shift_segment_right_bool();
+ fst_test_shift_segment_right_skip_start_node();
+ fst_test_const_iterator();
+ fst_test_insert_iterator();
+ fst_test_insert_state_changed();
+ fst_test_position_search();
+ }
+
+ if (opt.test_perf)
+ {
+ fst_perf_test_search(true);
+ fst_perf_test_search(false);
+ fst_perf_test_insert_front_back();
+ fst_perf_test_insert_position();
+ fst_perf_test_position_search();
+ }
+
fprintf(stdout, "Test finished successfully!\n");
return 0;
}
diff --git a/src/mixed_type_matrix_test.cpp b/src/mixed_type_matrix_test.cpp
index f3315ca..9e4a1ea 100644
--- a/src/mixed_type_matrix_test.cpp
+++ b/src/mixed_type_matrix_test.cpp
@@ -26,6 +26,7 @@
************************************************************************/
#include "mdds/mixed_type_matrix.hpp"
+#include "test_global.hpp"
#include <sstream>
#include <cassert>
@@ -33,47 +34,6 @@
#include <iostream>
#include <string>
-#include <stdio.h>
-#include <sys/time.h>
-
-namespace {
-
-class StackPrinter
-{
-public:
- explicit StackPrinter(const char* msg) :
- msMsg(msg)
- {
- fprintf(stdout, "%s: --begin\n", msMsg.c_str());
- mfStartTime = getTime();
- }
-
- ~StackPrinter()
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime));
- }
-
- void printTime(int line) const
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime));
- }
-
-private:
- double getTime() const
- {
- timeval tv;
- gettimeofday(&tv, NULL);
- return tv.tv_sec + tv.tv_usec / 1000000.0;
- }
-
- ::std::string msMsg;
- double mfStartTime;
-};
-
-}
-
using namespace std;
using namespace mdds;
@@ -879,31 +839,38 @@ void mtm_test_const_iterator()
assert(itr == itr_end); // not found.
}
-int main()
+int main(int argc, char** argv)
{
- run_tests_on_all_density_types(mtm_test_resize);
- run_tests_on_all_density_types(mtm_test_value_store);
- run_tests_on_all_density_types(mtm_test_transpose);
- run_tests_on_all_density_types(mtm_test_assignment);
-
- mtm_test_initial_elements();
- mtm_test_numeric_matrix();
- mtm_test_assign(matrix_density_filled_zero, matrix_density_filled_zero);
- mtm_test_assign(matrix_density_filled_empty, matrix_density_filled_zero);
- mtm_test_assign(matrix_density_filled_zero, matrix_density_filled_empty);
- mtm_test_assign(matrix_density_filled_empty, matrix_density_filled_empty);
-
- run_tests_on_all_density_types(mtm_test_flag_storage);
-
- mtm_test_iterator_access_filled(1, 1);
- mtm_test_iterator_access_filled(3, 1);
- mtm_test_iterator_access_filled(1, 3);
- mtm_test_iterator_access_filled(3, 3);
- mtm_test_iterator_access_filled(0, 0);
-
- mtm_test_iterator_access_sparse();
-
- mtm_test_const_iterator();
+ cmd_options opt;
+ if (!parse_cmd_options(argc, argv, opt))
+ return EXIT_FAILURE;
+
+ if (opt.test_func)
+ {
+ run_tests_on_all_density_types(mtm_test_resize);
+ run_tests_on_all_density_types(mtm_test_value_store);
+ run_tests_on_all_density_types(mtm_test_transpose);
+ run_tests_on_all_density_types(mtm_test_assignment);
+
+ mtm_test_initial_elements();
+ mtm_test_numeric_matrix();
+ mtm_test_assign(matrix_density_filled_zero, matrix_density_filled_zero);
+ mtm_test_assign(matrix_density_filled_empty, matrix_density_filled_zero);
+ mtm_test_assign(matrix_density_filled_zero, matrix_density_filled_empty);
+ mtm_test_assign(matrix_density_filled_empty, matrix_density_filled_empty);
+
+ run_tests_on_all_density_types(mtm_test_flag_storage);
+
+ mtm_test_iterator_access_filled(1, 1);
+ mtm_test_iterator_access_filled(3, 1);
+ mtm_test_iterator_access_filled(1, 3);
+ mtm_test_iterator_access_filled(3, 3);
+ mtm_test_iterator_access_filled(0, 0);
+
+ mtm_test_iterator_access_sparse();
+
+ mtm_test_const_iterator();
+ }
cout << "Test finished successfully!" << endl;
return EXIT_SUCCESS;
}
diff --git a/src/rectangle_set_test.cpp b/src/rectangle_set_test.cpp
index 40449c5..c335f39 100644
--- a/src/rectangle_set_test.cpp
+++ b/src/rectangle_set_test.cpp
@@ -26,53 +26,12 @@
************************************************************************/
#include "mdds/rectangle_set.hpp"
+#include "test_global.hpp"
#include <iostream>
#include <sstream>
#include <boost/ptr_container/ptr_vector.hpp>
-#include <stdio.h>
-#include <string>
-#include <sys/time.h>
-
-namespace {
-
-class StackPrinter
-{
-public:
- explicit StackPrinter(const char* msg) :
- msMsg(msg)
- {
- fprintf(stdout, "%s: --begin\n", msMsg.c_str());
- mfStartTime = getTime();
- }
-
- ~StackPrinter()
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime));
- }
-
- void printTime(int line) const
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime));
- }
-
-private:
- double getTime() const
- {
- timeval tv;
- gettimeofday(&tv, NULL);
- return tv.tv_sec + tv.tv_usec / 1000000.0;
- }
-
- ::std::string msMsg;
- double mfStartTime;
-};
-
-}
-
using namespace std;
using namespace mdds;
using ::boost::ptr_vector;
@@ -952,29 +911,10 @@ void rect_test_search_result_iterator()
int main(int argc, char** argv)
{
- bool test_func = false;
- bool test_perf = false;
- if (argc > 1)
- {
- for (int i = 1; i < argc; ++i)
- {
- if (!strncmp(argv[i], "func", 4))
- test_func = true;
- else if (!strncmp(argv[i], "perf", 4))
- test_perf = true;
- else
- {
- cout << "unknown argument: " << argv[i] << endl;
- return EXIT_FAILURE;
- }
- }
- }
- else
- {
- cout << "please specify test categories: [perf, func]" << endl;
+ cmd_options opt;
+ if (!parse_cmd_options(argc, argv, opt))
return EXIT_FAILURE;
- }
- if (test_func)
+ if (opt.test_func)
{
rect_test_insertion_removal();
rect_test_search();
@@ -984,7 +924,7 @@ int main(int argc, char** argv)
rect_test_search_result_iterator();
}
- if (test_perf)
+ if (opt.test_perf)
{
rect_test_perf_insertion_fixed_x();
rect_test_perf_insertion_fixed_y();
diff --git a/src/segment_tree_test.cpp b/src/segment_tree_test.cpp
index 9cf0b18..dc24758 100644
--- a/src/segment_tree_test.cpp
+++ b/src/segment_tree_test.cpp
@@ -27,13 +27,14 @@
#include "mdds/segment_tree.hpp"
+#include "test_global.hpp"
+
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
-#include <cstring>
#include <boost/ptr_container/ptr_vector.hpp>
@@ -43,46 +44,6 @@ using namespace std;
using namespace mdds;
using namespace boost;
-#include <sys/time.h>
-
-namespace {
-
-class StackPrinter
-{
-public:
- explicit StackPrinter(const char* msg) :
- msMsg(msg)
- {
- fprintf(stdout, "%s: --begin\n", msMsg.c_str());
- mfStartTime = getTime();
- }
-
- ~StackPrinter()
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime));
- }
-
- void printTime(int line) const
- {
- double fEndTime = getTime();
- fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime));
- }
-
-private:
- double getTime() const
- {
- timeval tv;
- gettimeofday(&tv, NULL);
- return tv.tv_sec + tv.tv_usec / 1000000.0;
- }
-
- ::std::string msMsg;
- double mfStartTime;
-};
-
-}
-
template<typename key_type, typename value_type>
void build_and_dump(segment_tree<key_type, value_type>&db)
{
@@ -1106,29 +1067,11 @@ void st_test_empty_result_set()
int main(int argc, char** argv)
{
- bool test_func = false;
- bool test_perf = false;
- if (argc > 1)
- {
- for (int i = 1; i < argc; ++i)
- {
- if (!strncmp(argv[i], "func", 4))
- test_func = true;
- else if (!strncmp(argv[i], "perf", 4))
- test_perf = true;
- else
- {
- cout << "unknown argument: " << argv[i] << endl;
- return EXIT_FAILURE;
- }
- }
- }
- else
- {
- cout << "please specify test categories: [perf, func]" << endl;
+ cmd_options opt;
+ if (!parse_cmd_options(argc, argv, opt))
return EXIT_FAILURE;
- }
- if (test_func)
+
+ if (opt.test_func)
{
st_test_insert_search_removal();
st_test_copy_constructor();
@@ -1144,7 +1087,7 @@ int main(int argc, char** argv)
st_test_empty_result_set();
}
- if (test_perf)
+ if (opt.test_perf)
{
st_test_perf_insertion();
}
diff --git a/src/test_global.hpp b/src/test_global.hpp
new file mode 100644
index 0000000..0e4f30b
--- /dev/null
+++ b/src/test_global.hpp
@@ -0,0 +1,107 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2010 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#ifndef __TEST_GLOBAL_HPP__
+#define __TEST_GLOBAL_HPP__
+
+#include <stdio.h>
+#include <string>
+#include <sys/time.h>
+
+#include <iostream>
+#include <cstring>
+
+struct cmd_options
+{
+ bool test_func;
+ bool test_perf;
+
+ cmd_options() : test_func(false), test_perf(false) {}
+};
+
+bool parse_cmd_options(int argc, char** argv, cmd_options& opt)
+{
+ using namespace std;
+
+ if (argc > 1)
+ {
+ for (int i = 1; i < argc; ++i)
+ {
+ if (!strncmp(argv[i], "func", 4))
+ opt.test_func = true;
+ else if (!strncmp(argv[i], "perf", 4))
+ opt.test_perf = true;
+ else
+ {
+ cout << "unknown argument: " << argv[i] << endl;
+ return false;
+ }
+ }
+ }
+ else
+ {
+ cout << "please specify test categories: [perf, func]" << endl;
+ return false;
+ }
+ return true;
+}
+
+class StackPrinter
+{
+public:
+ explicit StackPrinter(const char* msg) :
+ msMsg(msg)
+ {
+ fprintf(stdout, "%s: --begin\n", msMsg.c_str());
+ mfStartTime = getTime();
+ }
+
+ ~StackPrinter()
+ {
+ double fEndTime = getTime();
+ fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime));
+ }
+
+ void printTime(int line) const
+ {
+ double fEndTime = getTime();
+ fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime));
+ }
+
+private:
+ double getTime() const
+ {
+ timeval tv;
+ gettimeofday(&tv, NULL);
+ return tv.tv_sec + tv.tv_usec / 1000000.0;
+ }
+
+ ::std::string msMsg;
+ double mfStartTime;
+};
+
+#endif
--
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-openoffice/mdds.git
Reply to: