[mdds] 54/62: Imported Upstream version 0.12.1
This is an automated email from the git hooks/post-receive script.
rene pushed a commit to branch master
in repository mdds.
commit 94f701dab6d094ba60febf4d6bf91f5ecabd6ffe
Author: Rene Engelhard <rene@debian.org>
Date: Thu Apr 21 14:50:54 2016 +0200
Imported Upstream version 0.12.1
---
.gitignore | 13 +
NEWS | 8 +
configure | 32 +-
configure.ac | 2 +-
include/mdds/flat_segment_tree.hpp | 8 +-
include/mdds/multi_type_vector_types.hpp | 1 +
include/mdds/quad_node.hpp | 2 +
include/mdds/segment_tree.hpp | 541 +----------------------------
include/mdds/segment_tree_def.inl | 571 +++++++++++++++++++++++++++++++
src/flat_segment_tree_test.cpp | 37 ++
10 files changed, 654 insertions(+), 561 deletions(-)
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..70ade71
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,13 @@
+autom4te.cache/
+config.log
+config.status
+configure
+Makefile
+misc/mdds.pc
+obj/
+VERSION
+
+# tests
+*_test
+multi_type_vector_test_custom
+multi_type_vector_test_default
diff --git a/NEWS b/NEWS
index dd50612..ec531e6 100644
--- a/NEWS
+++ b/NEWS
@@ -1,3 +1,11 @@
+mdds 0.12.1
+
+* flat_segment_tree
+
+ * removed construction-from-int requirement from value_type to allow
+ non-numeric types to be stored.
+ * removed construction-from-int requirement from key_type as well.
+
mdds 0.12.0
* segment_tree
diff --git a/configure b/configure
index c228b58..5523151 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.69 for mdds 0.12.0.
+# Generated by GNU Autoconf 2.69 for mdds 0.12.1.
#
# Report bugs to <kohei.yoshida@gmail.com>.
#
@@ -579,8 +579,8 @@ MAKEFLAGS=
# Identity of this package.
PACKAGE_NAME='mdds'
PACKAGE_TARNAME='mdds'
-PACKAGE_VERSION='0.12.0'
-PACKAGE_STRING='mdds 0.12.0'
+PACKAGE_VERSION='0.12.1'
+PACKAGE_STRING='mdds 0.12.1'
PACKAGE_BUGREPORT='kohei.yoshida@gmail.com'
PACKAGE_URL=''
@@ -1181,7 +1181,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.12.0 to adapt to many kinds of systems.
+\`configure' configures mdds 0.12.1 to adapt to many kinds of systems.
Usage: $0 [OPTION]... [VAR=VALUE]...
@@ -1242,7 +1242,7 @@ fi
if test -n "$ac_init_help"; then
case $ac_init_help in
- short | recursive ) echo "Configuration of mdds 0.12.0:";;
+ short | recursive ) echo "Configuration of mdds 0.12.1:";;
esac
cat <<\_ACEOF
@@ -1335,7 +1335,7 @@ fi
test -n "$ac_init_help" && exit $ac_status
if $ac_init_version; then
cat <<\_ACEOF
-mdds configure 0.12.0
+mdds configure 0.12.1
generated by GNU Autoconf 2.69
Copyright (C) 2012 Free Software Foundation, Inc.
@@ -1352,7 +1352,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.12.0, which was
+It was created by mdds $as_me 0.12.1, which was
generated by GNU Autoconf 2.69. Invocation command line was
$ $0 $@
@@ -1701,7 +1701,7 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu
-VERSION=0.12.0
+VERSION=0.12.1
PACKAGE_TARNAME=mdds
@@ -2298,7 +2298,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=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.12.0, which was
+This file was extended by mdds $as_me 0.12.1, which was
generated by GNU Autoconf 2.69. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -2351,7 +2351,7 @@ _ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`"
ac_cs_version="\\
-mdds config.status 0.12.0
+mdds config.status 0.12.1
configured by $0, generated by GNU Autoconf 2.69,
with options \\"\$ac_cs_config\\"
@@ -3455,7 +3455,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=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.12.0, which was
+This file was extended by mdds $as_me 0.12.1, which was
generated by GNU Autoconf 2.69. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -3508,7 +3508,7 @@ _ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`"
ac_cs_version="\\
-mdds config.status 0.12.0
+mdds config.status 0.12.1
configured by $0, generated by GNU Autoconf 2.69,
with options \\"\$ac_cs_config\\"
@@ -4613,7 +4613,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=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.12.0, which was
+This file was extended by mdds $as_me 0.12.1, which was
generated by GNU Autoconf 2.69. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -4666,7 +4666,7 @@ _ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`"
ac_cs_version="\\
-mdds config.status 0.12.0
+mdds config.status 0.12.1
configured by $0, generated by GNU Autoconf 2.69,
with options \\"\$ac_cs_config\\"
@@ -5772,7 +5772,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=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.12.0, which was
+This file was extended by mdds $as_me 0.12.1, which was
generated by GNU Autoconf 2.69. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -5825,7 +5825,7 @@ _ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`"
ac_cs_version="\\
-mdds config.status 0.12.0
+mdds config.status 0.12.1
configured by $0, generated by GNU Autoconf 2.69,
with options \\"\$ac_cs_config\\"
diff --git a/configure.ac b/configure.ac
index d08631d..127ca75 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1,4 +1,4 @@
-AC_INIT(mdds, 0.12.0, kohei.yoshida@gmail.com)
+AC_INIT(mdds, 0.12.1, kohei.yoshida@gmail.com)
VERSION=AC_PACKAGE_VERSION
AC_SUBST(VERSION)
diff --git a/include/mdds/flat_segment_tree.hpp b/include/mdds/flat_segment_tree.hpp
index 3630c40..0e78eea 100644
--- a/include/mdds/flat_segment_tree.hpp
+++ b/include/mdds/flat_segment_tree.hpp
@@ -63,8 +63,8 @@ public:
}
nonleaf_value_type()
- : low(0)
- , high(0)
+ : low()
+ , high()
{
}
};
@@ -80,8 +80,8 @@ public:
}
leaf_value_type()
- : key(0)
- , value(0)
+ : key()
+ , value()
{
}
};
diff --git a/include/mdds/multi_type_vector_types.hpp b/include/mdds/multi_type_vector_types.hpp
index 0a36333..3899acd 100644
--- a/include/mdds/multi_type_vector_types.hpp
+++ b/include/mdds/multi_type_vector_types.hpp
@@ -33,6 +33,7 @@
#include "global.hpp"
#include <algorithm>
+#include <cassert>
#ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
#include <deque>
diff --git a/include/mdds/quad_node.hpp b/include/mdds/quad_node.hpp
index 4ece659..ab0b636 100644
--- a/include/mdds/quad_node.hpp
+++ b/include/mdds/quad_node.hpp
@@ -30,6 +30,8 @@
#include "mdds/global.hpp"
+#include <cassert>
+
#include <boost/intrusive_ptr.hpp>
namespace mdds {
diff --git a/include/mdds/segment_tree.hpp b/include/mdds/segment_tree.hpp
index 4bf18c6..e6b2dd8 100644
--- a/include/mdds/segment_tree.hpp
+++ b/include/mdds/segment_tree.hpp
@@ -770,547 +770,8 @@ private:
bool m_valid_tree:1;
};
-template<typename _Key, typename _Data>
-segment_tree<_Key, _Data>::segment_tree()
- : m_root_node(NULL)
- , m_valid_tree(false)
-{
-}
-
-template<typename _Key, typename _Data>
-segment_tree<_Key, _Data>::segment_tree(const segment_tree& r)
- : m_segment_data(r.m_segment_data)
- , m_root_node(NULL)
- , m_valid_tree(r.m_valid_tree)
-{
- if (m_valid_tree)
- build_tree();
-}
-
-template<typename _Key, typename _Data>
-segment_tree<_Key, _Data>::~segment_tree()
-{
- clear_all_nodes();
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::operator==(const segment_tree& r) const
-{
- if (m_valid_tree != r.m_valid_tree)
- return false;
-
- // Sort the data by key values first.
- sorted_segment_map_type seg1(m_segment_data.begin(), m_segment_data.end());
- sorted_segment_map_type seg2(r.m_segment_data.begin(), r.m_segment_data.end());
- typename sorted_segment_map_type::const_iterator itr1 = seg1.begin(), itr1_end = seg1.end();
- typename sorted_segment_map_type::const_iterator itr2 = seg2.begin(), itr2_end = seg2.end();
-
- for (; itr1 != itr1_end; ++itr1, ++itr2)
- {
- if (itr2 == itr2_end)
- return false;
-
- if (*itr1 != *itr2)
- return false;
- }
- if (itr2 != itr2_end)
- return false;
-
- return true;
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::build_tree()
-{
- build_leaf_nodes();
- m_nonleaf_node_pool.clear();
-
- // Count the number of leaf nodes.
- size_t leaf_count = __st::count_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
-
- // Determine the total number of non-leaf nodes needed to build the whole tree.
- size_t nonleaf_count = __st::count_needed_nonleaf_nodes(leaf_count);
-
- m_nonleaf_node_pool.resize(nonleaf_count);
-
- mdds::__st::tree_builder<segment_tree> builder(m_nonleaf_node_pool);
- m_root_node = builder.build(m_left_leaf);
-
- // Start "inserting" all segments from the root.
- typename segment_map_type::const_iterator itr,
- itr_beg = m_segment_data.begin(), itr_end = m_segment_data.end();
-
- data_node_map_type tagged_node_map;
- for (itr = itr_beg; itr != itr_end; ++itr)
- {
- data_type pdata = itr->first;
- ::std::pair<typename data_node_map_type::iterator, bool> r =
- tagged_node_map.insert(pdata, new node_list_type);
- node_list_type* plist = r.first->second;
- plist->reserve(10);
-
- descend_tree_and_mark(m_root_node, pdata, itr->second.first, itr->second.second, plist);
- }
-
- m_tagged_node_map.swap(tagged_node_map);
- m_valid_tree = true;
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::descend_tree_and_mark(
- __st::node_base* pnode, data_type pdata, key_type begin_key, key_type end_key, node_list_type* plist)
-{
- if (!pnode)
- return;
-
- if (pnode->is_leaf)
- {
- // This is a leaf node.
- node* pleaf = static_cast<node*>(pnode);
- if (begin_key <= pleaf->value_leaf.key && pleaf->value_leaf.key < end_key)
- {
- leaf_value_type& v = pleaf->value_leaf;
- if (!v.data_chain)
- v.data_chain = new data_chain_type;
- v.data_chain->push_back(pdata);
- plist->push_back(pnode);
- }
- return;
- }
-
- nonleaf_node* pnonleaf = static_cast<nonleaf_node*>(pnode);
- if (end_key < pnonleaf->value_nonleaf.low || pnonleaf->value_nonleaf.high <= begin_key)
- return;
-
- nonleaf_value_type& v = pnonleaf->value_nonleaf;
- if (begin_key <= v.low && v.high < end_key)
- {
- // mark this non-leaf node and stop.
- if (!v.data_chain)
- v.data_chain = new data_chain_type;
- v.data_chain->push_back(pdata);
- plist->push_back(pnode);
- return;
- }
-
- descend_tree_and_mark(pnonleaf->left, pdata, begin_key, end_key, plist);
- descend_tree_and_mark(pnonleaf->right, pdata, begin_key, end_key, plist);
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::build_leaf_nodes()
-{
- using namespace std;
-
- disconnect_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
-
- // In 1st pass, collect unique end-point values and sort them.
- vector<key_type> keys_uniq;
- keys_uniq.reserve(m_segment_data.size()*2);
- typename segment_map_type::const_iterator itr, itr_beg = m_segment_data.begin(), itr_end = m_segment_data.end();
- for (itr = itr_beg; itr != itr_end; ++itr)
- {
- keys_uniq.push_back(itr->second.first);
- keys_uniq.push_back(itr->second.second);
- }
-
- // sort and remove duplicates.
- sort(keys_uniq.begin(), keys_uniq.end());
- keys_uniq.erase(unique(keys_uniq.begin(), keys_uniq.end()), keys_uniq.end());
-
- create_leaf_node_instances(keys_uniq, m_left_leaf, m_right_leaf);
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::create_leaf_node_instances(const ::std::vector<key_type>& keys, node_ptr& left, node_ptr& right)
-{
- if (keys.empty() || keys.size() < 2)
- // We need at least two keys in order to build tree.
- return;
-
- typename ::std::vector<key_type>::const_iterator itr = keys.begin(), itr_end = keys.end();
-
- // left-most node
- left.reset(new node);
- left->value_leaf.key = *itr;
-
- // move on to next.
- left->next.reset(new node);
- node_ptr prev_node = left;
- node_ptr cur_node = left->next;
- cur_node->prev = prev_node;
-
- for (++itr; itr != itr_end; ++itr)
- {
- cur_node->value_leaf.key = *itr;
-
- // move on to next
- cur_node->next.reset(new node);
- prev_node = cur_node;
- cur_node = cur_node->next;
- cur_node->prev = prev_node;
- }
-
- // Remove the excess node.
- prev_node->next.reset();
- right = prev_node;
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::insert(key_type begin_key, key_type end_key, data_type pdata)
-{
- if (begin_key >= end_key)
- return false;
-
- if (m_segment_data.find(pdata) != m_segment_data.end())
- // Insertion of duplicate data is not allowed.
- return false;
-
- ::std::pair<key_type, key_type> range;
- range.first = begin_key;
- range.second = end_key;
- m_segment_data.insert(typename segment_map_type::value_type(pdata, range));
-
- m_valid_tree = false;
- return true;
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::search(key_type point, search_result_type& result) const
-{
- if (!m_valid_tree)
- // Tree is invalidated.
- return false;
-
- if (!m_root_node)
- // Tree doesn't exist. Since the tree is flagged valid, this means no
- // segments have been inserted.
- return true;
-
- search_result_vector_inserter result_inserter(result);
- typedef segment_tree<_Key,_Data> tree_type;
- __st::descend_tree_for_search<
- tree_type, search_result_vector_inserter>(point, m_root_node, result_inserter);
- return true;
-}
-
-template<typename _Key, typename _Data>
-typename segment_tree<_Key, _Data>::search_result
-segment_tree<_Key, _Data>::search(key_type point) const
-{
- search_result result;
- if (!m_valid_tree || !m_root_node)
- return result;
-
- search_result_inserter result_inserter(result);
- typedef segment_tree<_Key,_Data> tree_type;
- __st::descend_tree_for_search<tree_type, search_result_inserter>(
- point, m_root_node, result_inserter);
-
- return result;
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::search(key_type point, search_result_base& result) const
-{
- if (!m_valid_tree || !m_root_node)
- return;
-
- search_result_inserter result_inserter(result);
- typedef segment_tree<_Key,_Data> tree_type;
- __st::descend_tree_for_search<tree_type>(point, m_root_node, result_inserter);
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::remove(data_type pdata)
-{
- using namespace std;
-
- typename data_node_map_type::iterator itr = m_tagged_node_map.find(pdata);
- if (itr != m_tagged_node_map.end())
- {
- // Tagged node list found. Remove all the tags from the tree nodes.
- node_list_type* plist = itr->second;
- if (!plist)
- return;
-
- remove_data_from_nodes(plist, pdata);
-
- // Remove the tags associated with this pointer from the data set.
- m_tagged_node_map.erase(itr);
- }
-
- // Remove from the segment data array.
- m_segment_data.erase(pdata);
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::clear()
-{
- m_tagged_node_map.clear();
- m_segment_data.clear();
- clear_all_nodes();
- m_valid_tree = false;
-}
-
-template<typename _Key, typename _Data>
-size_t segment_tree<_Key, _Data>::size() const
-{
- return m_segment_data.size();
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::empty() const
-{
- return m_segment_data.empty();
-}
-
-template<typename _Key, typename _Value>
-size_t segment_tree<_Key, _Value>::leaf_size() const
-{
- return __st::count_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::remove_data_from_nodes(node_list_type* plist, const data_type pdata)
-{
- typename node_list_type::iterator itr = plist->begin(), itr_end = plist->end();
- for (; itr != itr_end; ++itr)
- {
- data_chain_type* chain = NULL;
- __st::node_base* p = *itr;
- if (p->is_leaf)
- chain = static_cast<node*>(p)->value_leaf.data_chain;
- else
- chain = static_cast<nonleaf_node*>(p)->value_nonleaf.data_chain;
-
- if (!chain)
- continue;
-
- remove_data_from_chain(*chain, pdata);
- }
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::remove_data_from_chain(data_chain_type& chain, const data_type pdata)
-{
- typename data_chain_type::iterator itr = ::std::find(chain.begin(), chain.end(), pdata);
- if (itr != chain.end())
- {
- *itr = chain.back();
- chain.pop_back();
- }
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::clear_all_nodes()
-{
- disconnect_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
- m_nonleaf_node_pool.clear();
- m_left_leaf.reset();
- m_right_leaf.reset();
- m_root_node = NULL;
-}
-
-#ifdef MDDS_UNIT_TEST
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::dump_tree() const
-{
- using ::std::cout;
- using ::std::endl;
-
- if (!m_valid_tree)
- assert(!"attempted to dump an invalid tree!");
-
- cout << "dump tree ------------------------------------------------------" << endl;
- size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
- size_t node_instance_count = node::get_instance_count();
-
- cout << "tree node count = " << node_count << " node instance count = " << node_instance_count << endl;
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::dump_leaf_nodes() const
-{
- using ::std::cout;
- using ::std::endl;
-
- cout << "dump leaf nodes ------------------------------------------------" << endl;
-
- node* p = m_left_leaf.get();
- while (p)
- {
- print_leaf_value(p->value_leaf);
- p = p->next.get();
- }
- cout << " node instance count = " << node::get_instance_count() << endl;
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::dump_segment_data() const
-{
- using namespace std;
- cout << "dump segment data ----------------------------------------------" << endl;
-
- segment_map_printer func;
- for_each(m_segment_data.begin(), m_segment_data.end(), func);
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::verify_node_lists() const
-{
- using namespace std;
-
- typename data_node_map_type::const_iterator
- itr = m_tagged_node_map.begin(), itr_end = m_tagged_node_map.end();
- for (; itr != itr_end; ++itr)
- {
- // Print stored nodes.
- cout << "node list " << itr->first->name << ": ";
- const node_list_type* plist = itr->second;
- assert(plist);
- node_printer func;
- for_each(plist->begin(), plist->end(), func);
- cout << endl;
-
- // Verify that all of these nodes have the data pointer.
- if (!has_data_pointer(*plist, itr->first))
- return false;
- }
- return true;
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::verify_leaf_nodes(const ::std::vector<leaf_node_check>& checks) const
-{
- using namespace std;
-
- node* cur_node = m_left_leaf.get();
- typename ::std::vector<leaf_node_check>::const_iterator itr = checks.begin(), itr_end = checks.end();
- for (; itr != itr_end; ++itr)
- {
- if (!cur_node)
- // Position past the right-mode node. Invalid.
- return false;
-
- if (cur_node->value_leaf.key != itr->key)
- // Key values differ.
- return false;
-
- if (itr->data_chain.empty())
- {
- if (cur_node->value_leaf.data_chain)
- // The data chain should be empty (i.e. the pointer should be NULL).
- return false;
- }
- else
- {
- if (!cur_node->value_leaf.data_chain)
- // This node should have data pointers!
- return false;
-
- data_chain_type chain1 = itr->data_chain;
- data_chain_type chain2 = *cur_node->value_leaf.data_chain;
-
- if (chain1.size() != chain2.size())
- return false;
-
- ::std::vector<data_type> test1, test2;
- test1.reserve(chain1.size());
- test2.reserve(chain2.size());
- copy(chain1.begin(), chain1.end(), back_inserter(test1));
- copy(chain2.begin(), chain2.end(), back_inserter(test2));
-
- // Sort both arrays before comparing them.
- sort(test1.begin(), test1.end());
- sort(test2.begin(), test2.end());
-
- if (test1 != test2)
- return false;
- }
-
- cur_node = cur_node->next.get();
- }
-
- if (cur_node)
- // At this point, we expect the current node to be at the position
- // past the right-most node, which is NULL.
- return false;
-
- return true;
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::verify_segment_data(const segment_map_type& checks) const
-{
- // Sort the data by key values first.
- sorted_segment_map_type seg1(checks.begin(), checks.end());
- sorted_segment_map_type seg2(m_segment_data.begin(), m_segment_data.end());
-
- typename sorted_segment_map_type::const_iterator itr1 = seg1.begin(), itr1_end = seg1.end();
- typename sorted_segment_map_type::const_iterator itr2 = seg2.begin(), itr2_end = seg2.end();
- for (; itr1 != itr1_end; ++itr1, ++itr2)
- {
- if (itr2 == itr2_end)
- return false;
-
- if (*itr1 != *itr2)
- return false;
- }
- if (itr2 != itr2_end)
- return false;
-
- return true;
-}
-
-template<typename _Key, typename _Data>
-bool segment_tree<_Key, _Data>::has_data_pointer(const node_list_type& node_list, const data_type pdata)
-{
- using namespace std;
-
- typename node_list_type::const_iterator
- itr = node_list.begin(), itr_end = node_list.end();
-
- for (; itr != itr_end; ++itr)
- {
- // Check each node, and make sure each node has the pdata pointer
- // listed.
- const __st::node_base* pnode = *itr;
- const data_chain_type* chain = NULL;
- if (pnode->is_leaf)
- chain = static_cast<const node*>(pnode)->value_leaf.data_chain;
- else
- chain = static_cast<const nonleaf_node*>(pnode)->value_nonleaf.data_chain;
-
- if (!chain)
- return false;
-
- if (find(chain->begin(), chain->end(), pdata) == chain->end())
- return false;
- }
- return true;
-}
-
-template<typename _Key, typename _Data>
-void segment_tree<_Key, _Data>::print_leaf_value(const leaf_value_type& v)
-{
- using namespace std;
- cout << v.key << ": { ";
- if (v.data_chain)
- {
- const data_chain_type* pchain = v.data_chain;
- typename data_chain_type::const_iterator itr, itr_beg = pchain->begin(), itr_end = pchain->end();
- for (itr = itr_beg; itr != itr_end; ++itr)
- {
- if (itr != itr_beg)
- cout << ", ";
- cout << (*itr)->name;
- }
- }
- cout << " }" << endl;
}
-#endif
-}
+#include "segment_tree_def.inl"
#endif
diff --git a/include/mdds/segment_tree_def.inl b/include/mdds/segment_tree_def.inl
new file mode 100644
index 0000000..3120a27
--- /dev/null
+++ b/include/mdds/segment_tree_def.inl
@@ -0,0 +1,571 @@
+/*************************************************************************
+*
+* Copyright (c) 2015 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 _Data>
+segment_tree<_Key, _Data>::segment_tree()
+ : m_root_node(NULL)
+ , m_valid_tree(false)
+{
+}
+
+template<typename _Key, typename _Data>
+segment_tree<_Key, _Data>::segment_tree(const segment_tree& r)
+ : m_segment_data(r.m_segment_data)
+ , m_root_node(NULL)
+ , m_valid_tree(r.m_valid_tree)
+{
+ if (m_valid_tree)
+ build_tree();
+}
+
+template<typename _Key, typename _Data>
+segment_tree<_Key, _Data>::~segment_tree()
+{
+ clear_all_nodes();
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::operator==(const segment_tree& r) const
+{
+ if (m_valid_tree != r.m_valid_tree)
+ return false;
+
+ // Sort the data by key values first.
+ sorted_segment_map_type seg1(m_segment_data.begin(), m_segment_data.end());
+ sorted_segment_map_type seg2(r.m_segment_data.begin(), r.m_segment_data.end());
+ typename sorted_segment_map_type::const_iterator itr1 = seg1.begin(), itr1_end = seg1.end();
+ typename sorted_segment_map_type::const_iterator itr2 = seg2.begin(), itr2_end = seg2.end();
+
+ for (; itr1 != itr1_end; ++itr1, ++itr2)
+ {
+ if (itr2 == itr2_end)
+ return false;
+
+ if (*itr1 != *itr2)
+ return false;
+ }
+ if (itr2 != itr2_end)
+ return false;
+
+ return true;
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::build_tree()
+{
+ build_leaf_nodes();
+ m_nonleaf_node_pool.clear();
+
+ // Count the number of leaf nodes.
+ size_t leaf_count = __st::count_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
+
+ // Determine the total number of non-leaf nodes needed to build the whole tree.
+ size_t nonleaf_count = __st::count_needed_nonleaf_nodes(leaf_count);
+
+ m_nonleaf_node_pool.resize(nonleaf_count);
+
+ mdds::__st::tree_builder<segment_tree> builder(m_nonleaf_node_pool);
+ m_root_node = builder.build(m_left_leaf);
+
+ // Start "inserting" all segments from the root.
+ typename segment_map_type::const_iterator itr,
+ itr_beg = m_segment_data.begin(), itr_end = m_segment_data.end();
+
+ data_node_map_type tagged_node_map;
+ for (itr = itr_beg; itr != itr_end; ++itr)
+ {
+ data_type pdata = itr->first;
+ ::std::pair<typename data_node_map_type::iterator, bool> r =
+ tagged_node_map.insert(pdata, new node_list_type);
+ node_list_type* plist = r.first->second;
+ plist->reserve(10);
+
+ descend_tree_and_mark(m_root_node, pdata, itr->second.first, itr->second.second, plist);
+ }
+
+ m_tagged_node_map.swap(tagged_node_map);
+ m_valid_tree = true;
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::descend_tree_and_mark(
+ __st::node_base* pnode, data_type pdata, key_type begin_key, key_type end_key, node_list_type* plist)
+{
+ if (!pnode)
+ return;
+
+ if (pnode->is_leaf)
+ {
+ // This is a leaf node.
+ node* pleaf = static_cast<node*>(pnode);
+ if (begin_key <= pleaf->value_leaf.key && pleaf->value_leaf.key < end_key)
+ {
+ leaf_value_type& v = pleaf->value_leaf;
+ if (!v.data_chain)
+ v.data_chain = new data_chain_type;
+ v.data_chain->push_back(pdata);
+ plist->push_back(pnode);
+ }
+ return;
+ }
+
+ nonleaf_node* pnonleaf = static_cast<nonleaf_node*>(pnode);
+ if (end_key < pnonleaf->value_nonleaf.low || pnonleaf->value_nonleaf.high <= begin_key)
+ return;
+
+ nonleaf_value_type& v = pnonleaf->value_nonleaf;
+ if (begin_key <= v.low && v.high < end_key)
+ {
+ // mark this non-leaf node and stop.
+ if (!v.data_chain)
+ v.data_chain = new data_chain_type;
+ v.data_chain->push_back(pdata);
+ plist->push_back(pnode);
+ return;
+ }
+
+ descend_tree_and_mark(pnonleaf->left, pdata, begin_key, end_key, plist);
+ descend_tree_and_mark(pnonleaf->right, pdata, begin_key, end_key, plist);
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::build_leaf_nodes()
+{
+ using namespace std;
+
+ disconnect_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
+
+ // In 1st pass, collect unique end-point values and sort them.
+ vector<key_type> keys_uniq;
+ keys_uniq.reserve(m_segment_data.size()*2);
+ typename segment_map_type::const_iterator itr, itr_beg = m_segment_data.begin(), itr_end = m_segment_data.end();
+ for (itr = itr_beg; itr != itr_end; ++itr)
+ {
+ keys_uniq.push_back(itr->second.first);
+ keys_uniq.push_back(itr->second.second);
+ }
+
+ // sort and remove duplicates.
+ sort(keys_uniq.begin(), keys_uniq.end());
+ keys_uniq.erase(unique(keys_uniq.begin(), keys_uniq.end()), keys_uniq.end());
+
+ create_leaf_node_instances(keys_uniq, m_left_leaf, m_right_leaf);
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::create_leaf_node_instances(const ::std::vector<key_type>& keys, node_ptr& left, node_ptr& right)
+{
+ if (keys.empty() || keys.size() < 2)
+ // We need at least two keys in order to build tree.
+ return;
+
+ typename ::std::vector<key_type>::const_iterator itr = keys.begin(), itr_end = keys.end();
+
+ // left-most node
+ left.reset(new node);
+ left->value_leaf.key = *itr;
+
+ // move on to next.
+ left->next.reset(new node);
+ node_ptr prev_node = left;
+ node_ptr cur_node = left->next;
+ cur_node->prev = prev_node;
+
+ for (++itr; itr != itr_end; ++itr)
+ {
+ cur_node->value_leaf.key = *itr;
+
+ // move on to next
+ cur_node->next.reset(new node);
+ prev_node = cur_node;
+ cur_node = cur_node->next;
+ cur_node->prev = prev_node;
+ }
+
+ // Remove the excess node.
+ prev_node->next.reset();
+ right = prev_node;
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::insert(key_type begin_key, key_type end_key, data_type pdata)
+{
+ if (begin_key >= end_key)
+ return false;
+
+ if (m_segment_data.find(pdata) != m_segment_data.end())
+ // Insertion of duplicate data is not allowed.
+ return false;
+
+ ::std::pair<key_type, key_type> range;
+ range.first = begin_key;
+ range.second = end_key;
+ m_segment_data.insert(typename segment_map_type::value_type(pdata, range));
+
+ m_valid_tree = false;
+ return true;
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::search(key_type point, search_result_type& result) const
+{
+ if (!m_valid_tree)
+ // Tree is invalidated.
+ return false;
+
+ if (!m_root_node)
+ // Tree doesn't exist. Since the tree is flagged valid, this means no
+ // segments have been inserted.
+ return true;
+
+ search_result_vector_inserter result_inserter(result);
+ typedef segment_tree<_Key,_Data> tree_type;
+ __st::descend_tree_for_search<
+ tree_type, search_result_vector_inserter>(point, m_root_node, result_inserter);
+ return true;
+}
+
+template<typename _Key, typename _Data>
+typename segment_tree<_Key, _Data>::search_result
+segment_tree<_Key, _Data>::search(key_type point) const
+{
+ search_result result;
+ if (!m_valid_tree || !m_root_node)
+ return result;
+
+ search_result_inserter result_inserter(result);
+ typedef segment_tree<_Key,_Data> tree_type;
+ __st::descend_tree_for_search<tree_type, search_result_inserter>(
+ point, m_root_node, result_inserter);
+
+ return result;
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::search(key_type point, search_result_base& result) const
+{
+ if (!m_valid_tree || !m_root_node)
+ return;
+
+ search_result_inserter result_inserter(result);
+ typedef segment_tree<_Key,_Data> tree_type;
+ __st::descend_tree_for_search<tree_type>(point, m_root_node, result_inserter);
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::remove(data_type pdata)
+{
+ using namespace std;
+
+ typename data_node_map_type::iterator itr = m_tagged_node_map.find(pdata);
+ if (itr != m_tagged_node_map.end())
+ {
+ // Tagged node list found. Remove all the tags from the tree nodes.
+ node_list_type* plist = itr->second;
+ if (!plist)
+ return;
+
+ remove_data_from_nodes(plist, pdata);
+
+ // Remove the tags associated with this pointer from the data set.
+ m_tagged_node_map.erase(itr);
+ }
+
+ // Remove from the segment data array.
+ m_segment_data.erase(pdata);
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::clear()
+{
+ m_tagged_node_map.clear();
+ m_segment_data.clear();
+ clear_all_nodes();
+ m_valid_tree = false;
+}
+
+template<typename _Key, typename _Data>
+size_t segment_tree<_Key, _Data>::size() const
+{
+ return m_segment_data.size();
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::empty() const
+{
+ return m_segment_data.empty();
+}
+
+template<typename _Key, typename _Value>
+size_t segment_tree<_Key, _Value>::leaf_size() const
+{
+ return __st::count_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::remove_data_from_nodes(node_list_type* plist, const data_type pdata)
+{
+ typename node_list_type::iterator itr = plist->begin(), itr_end = plist->end();
+ for (; itr != itr_end; ++itr)
+ {
+ data_chain_type* chain = NULL;
+ __st::node_base* p = *itr;
+ if (p->is_leaf)
+ chain = static_cast<node*>(p)->value_leaf.data_chain;
+ else
+ chain = static_cast<nonleaf_node*>(p)->value_nonleaf.data_chain;
+
+ if (!chain)
+ continue;
+
+ remove_data_from_chain(*chain, pdata);
+ }
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::remove_data_from_chain(data_chain_type& chain, const data_type pdata)
+{
+ typename data_chain_type::iterator itr = ::std::find(chain.begin(), chain.end(), pdata);
+ if (itr != chain.end())
+ {
+ *itr = chain.back();
+ chain.pop_back();
+ }
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::clear_all_nodes()
+{
+ disconnect_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
+ m_nonleaf_node_pool.clear();
+ m_left_leaf.reset();
+ m_right_leaf.reset();
+ m_root_node = NULL;
+}
+
+#ifdef MDDS_UNIT_TEST
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::dump_tree() const
+{
+ using ::std::cout;
+ using ::std::endl;
+
+ if (!m_valid_tree)
+ assert(!"attempted to dump an invalid tree!");
+
+ cout << "dump tree ------------------------------------------------------" << endl;
+ size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
+ size_t node_instance_count = node::get_instance_count();
+
+ cout << "tree node count = " << node_count << " node instance count = " << node_instance_count << endl;
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::dump_leaf_nodes() const
+{
+ using ::std::cout;
+ using ::std::endl;
+
+ cout << "dump leaf nodes ------------------------------------------------" << endl;
+
+ node* p = m_left_leaf.get();
+ while (p)
+ {
+ print_leaf_value(p->value_leaf);
+ p = p->next.get();
+ }
+ cout << " node instance count = " << node::get_instance_count() << endl;
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::dump_segment_data() const
+{
+ using namespace std;
+ cout << "dump segment data ----------------------------------------------" << endl;
+
+ segment_map_printer func;
+ for_each(m_segment_data.begin(), m_segment_data.end(), func);
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::verify_node_lists() const
+{
+ using namespace std;
+
+ typename data_node_map_type::const_iterator
+ itr = m_tagged_node_map.begin(), itr_end = m_tagged_node_map.end();
+ for (; itr != itr_end; ++itr)
+ {
+ // Print stored nodes.
+ cout << "node list " << itr->first->name << ": ";
+ const node_list_type* plist = itr->second;
+ assert(plist);
+ node_printer func;
+ for_each(plist->begin(), plist->end(), func);
+ cout << endl;
+
+ // Verify that all of these nodes have the data pointer.
+ if (!has_data_pointer(*plist, itr->first))
+ return false;
+ }
+ return true;
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::verify_leaf_nodes(const ::std::vector<leaf_node_check>& checks) const
+{
+ using namespace std;
+
+ node* cur_node = m_left_leaf.get();
+ typename ::std::vector<leaf_node_check>::const_iterator itr = checks.begin(), itr_end = checks.end();
+ for (; itr != itr_end; ++itr)
+ {
+ if (!cur_node)
+ // Position past the right-mode node. Invalid.
+ return false;
+
+ if (cur_node->value_leaf.key != itr->key)
+ // Key values differ.
+ return false;
+
+ if (itr->data_chain.empty())
+ {
+ if (cur_node->value_leaf.data_chain)
+ // The data chain should be empty (i.e. the pointer should be NULL).
+ return false;
+ }
+ else
+ {
+ if (!cur_node->value_leaf.data_chain)
+ // This node should have data pointers!
+ return false;
+
+ data_chain_type chain1 = itr->data_chain;
+ data_chain_type chain2 = *cur_node->value_leaf.data_chain;
+
+ if (chain1.size() != chain2.size())
+ return false;
+
+ ::std::vector<data_type> test1, test2;
+ test1.reserve(chain1.size());
+ test2.reserve(chain2.size());
+ copy(chain1.begin(), chain1.end(), back_inserter(test1));
+ copy(chain2.begin(), chain2.end(), back_inserter(test2));
+
+ // Sort both arrays before comparing them.
+ sort(test1.begin(), test1.end());
+ sort(test2.begin(), test2.end());
+
+ if (test1 != test2)
+ return false;
+ }
+
+ cur_node = cur_node->next.get();
+ }
+
+ if (cur_node)
+ // At this point, we expect the current node to be at the position
+ // past the right-most node, which is NULL.
+ return false;
+
+ return true;
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::verify_segment_data(const segment_map_type& checks) const
+{
+ // Sort the data by key values first.
+ sorted_segment_map_type seg1(checks.begin(), checks.end());
+ sorted_segment_map_type seg2(m_segment_data.begin(), m_segment_data.end());
+
+ typename sorted_segment_map_type::const_iterator itr1 = seg1.begin(), itr1_end = seg1.end();
+ typename sorted_segment_map_type::const_iterator itr2 = seg2.begin(), itr2_end = seg2.end();
+ for (; itr1 != itr1_end; ++itr1, ++itr2)
+ {
+ if (itr2 == itr2_end)
+ return false;
+
+ if (*itr1 != *itr2)
+ return false;
+ }
+ if (itr2 != itr2_end)
+ return false;
+
+ return true;
+}
+
+template<typename _Key, typename _Data>
+bool segment_tree<_Key, _Data>::has_data_pointer(const node_list_type& node_list, const data_type pdata)
+{
+ using namespace std;
+
+ typename node_list_type::const_iterator
+ itr = node_list.begin(), itr_end = node_list.end();
+
+ for (; itr != itr_end; ++itr)
+ {
+ // Check each node, and make sure each node has the pdata pointer
+ // listed.
+ const __st::node_base* pnode = *itr;
+ const data_chain_type* chain = NULL;
+ if (pnode->is_leaf)
+ chain = static_cast<const node*>(pnode)->value_leaf.data_chain;
+ else
+ chain = static_cast<const nonleaf_node*>(pnode)->value_nonleaf.data_chain;
+
+ if (!chain)
+ return false;
+
+ if (find(chain->begin(), chain->end(), pdata) == chain->end())
+ return false;
+ }
+ return true;
+}
+
+template<typename _Key, typename _Data>
+void segment_tree<_Key, _Data>::print_leaf_value(const leaf_value_type& v)
+{
+ using namespace std;
+ cout << v.key << ": { ";
+ if (v.data_chain)
+ {
+ const data_chain_type* pchain = v.data_chain;
+ typename data_chain_type::const_iterator itr, itr_beg = pchain->begin(), itr_end = pchain->end();
+ for (itr = itr_beg; itr != itr_end; ++itr)
+ {
+ if (itr != itr_beg)
+ cout << ", ";
+ cout << (*itr)->name;
+ }
+ }
+ cout << " }" << endl;
+}
+#endif
+
+}
diff --git a/src/flat_segment_tree_test.cpp b/src/flat_segment_tree_test.cpp
index cb1601c..ff94bba 100644
--- a/src/flat_segment_tree_test.cpp
+++ b/src/flat_segment_tree_test.cpp
@@ -30,6 +30,7 @@
#include <list>
#include <iostream>
+#include <string>
#include <vector>
#include <limits>
#include <iterator>
@@ -1928,6 +1929,40 @@ void fst_test_assignment()
assert(!db3.is_tree_valid());
}
+void fst_test_non_numeric_value()
+{
+ stack_printer __stack_printer__("::fst_test_non_numeric_value");
+
+ typedef flat_segment_tree<int, std::string> db_type;
+ db_type db(0, 4, "42");
+ db.insert_back(1, 2, "hello world");
+
+ assert(db.default_value() == "42");
+
+ std::string result;
+ db.search(1, result);
+
+ assert(result == "hello world");
+}
+
+void fst_test_non_numeric_key()
+{
+ stack_printer __stack_printer__("::fst_test_non_numeric_key");
+
+ typedef flat_segment_tree<std::string, int> db_type;
+ db_type db("a", "h", 42);
+ db.insert_back("c", "f", 1);
+
+ assert(db.default_value() == 42);
+
+ int result(0);
+
+ db.search("d", result);
+ assert(result == 1);
+ db.search("f", result);
+ assert(result == 42);
+}
+
int main (int argc, char **argv)
{
try
@@ -1982,6 +2017,8 @@ int main (int argc, char **argv)
fst_test_swap();
fst_test_clear();
fst_test_assignment();
+ fst_test_non_numeric_value();
+ fst_test_non_numeric_key();
}
if (opt.test_perf)
--
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-openoffice/mdds.git
Reply to: