Hello community,
here is the log from the commit of package mdds for openSUSE:Factory checked in at 2015-07-02 22:46:03
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/mdds (Old)
and /work/SRC/openSUSE:Factory/.mdds.new (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "mdds"
Changes:
--------
--- /work/SRC/openSUSE:Factory/mdds/mdds.changes 2015-04-05 02:02:52.000000000 +0200
+++ /work/SRC/openSUSE:Factory/.mdds.new/mdds.changes 2015-07-02 22:46:04.000000000 +0200
@@ -1,0 +2,6 @@
+Wed Jun 24 12:04:51 UTC 2015 - tchvatal@suse.com
+
+- Version bump to 0.12.1:
+ * Various small fixes on 0.12 series
+
+-------------------------------------------------------------------
Old:
----
mdds_0.12.0.tar.bz2
New:
----
mdds_0.12.1.tar.bz2
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ mdds.spec ++++++
--- /var/tmp/diff_new_pack.mXOtGu/_old 2015-07-02 22:46:05.000000000 +0200
+++ /var/tmp/diff_new_pack.mXOtGu/_new 2015-07-02 22:46:05.000000000 +0200
@@ -19,7 +19,7 @@
# redefined as we put there just devel docs
%define _docdir %{_defaultdocdir}/%{name}-devel
Name: mdds
-Version: 0.12.0
+Version: 0.12.1
Release: 0
Summary: A collection of multi-dimensional data structure and indexing algorithm
License: MIT
++++++ mdds_0.12.0.tar.bz2 -> mdds_0.12.1.tar.bz2 ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/.gitignore new/mdds_0.12.1/.gitignore
--- old/mdds_0.12.0/.gitignore 1970-01-01 01:00:00.000000000 +0100
+++ new/mdds_0.12.1/.gitignore 2015-06-12 01:53:55.000000000 +0200
@@ -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 -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/NEWS new/mdds_0.12.1/NEWS
--- old/mdds_0.12.0/NEWS 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/NEWS 2015-06-12 01:53:55.000000000 +0200
@@ -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 -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/configure new/mdds_0.12.1/configure
--- old/mdds_0.12.0/configure 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/configure 2015-06-12 01:53:55.000000000 +0200
@@ -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 .
#
@@ -579,8 +579,8 @@
# 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 @@
# 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 @@
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 @@
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 @@
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 @@
-VERSION=0.12.0
+VERSION=0.12.1
PACKAGE_TARNAME=mdds
@@ -2298,7 +2298,7 @@
# 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 @@
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 @@
# 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 @@
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 @@
# 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 @@
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 @@
# 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 @@
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 -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/configure.ac new/mdds_0.12.1/configure.ac
--- old/mdds_0.12.0/configure.ac 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/configure.ac 2015-06-12 01:53:55.000000000 +0200
@@ -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 -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/include/mdds/flat_segment_tree.hpp new/mdds_0.12.1/include/mdds/flat_segment_tree.hpp
--- old/mdds_0.12.0/include/mdds/flat_segment_tree.hpp 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/include/mdds/flat_segment_tree.hpp 2015-06-12 01:53:55.000000000 +0200
@@ -63,8 +63,8 @@
}
nonleaf_value_type()
- : low(0)
- , high(0)
+ : low()
+ , high()
{
}
};
@@ -80,8 +80,8 @@
}
leaf_value_type()
- : key(0)
- , value(0)
+ : key()
+ , value()
{
}
};
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/include/mdds/multi_type_vector_types.hpp new/mdds_0.12.1/include/mdds/multi_type_vector_types.hpp
--- old/mdds_0.12.0/include/mdds/multi_type_vector_types.hpp 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/include/mdds/multi_type_vector_types.hpp 2015-06-12 01:53:55.000000000 +0200
@@ -33,6 +33,7 @@
#include "global.hpp"
#include <algorithm>
+#include <cassert>
#ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
#include <deque>
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/include/mdds/quad_node.hpp new/mdds_0.12.1/include/mdds/quad_node.hpp
--- old/mdds_0.12.0/include/mdds/quad_node.hpp 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/include/mdds/quad_node.hpp 2015-06-12 01:53:55.000000000 +0200
@@ -30,6 +30,8 @@
#include "mdds/global.hpp"
+#include <cassert>
+
#include
namespace mdds {
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/include/mdds/segment_tree.hpp new/mdds_0.12.1/include/mdds/segment_tree.hpp
--- old/mdds_0.12.0/include/mdds/segment_tree.hpp 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/include/mdds/segment_tree.hpp 2015-06-12 01:53:55.000000000 +0200
@@ -770,547 +770,8 @@
bool m_valid_tree:1;
};
-template
-segment_tree<_Key, _Data>::segment_tree()
- : m_root_node(NULL)
- , m_valid_tree(false)
-{
}
-template
-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
-segment_tree<_Key, _Data>::~segment_tree()
-{
- clear_all_nodes();
-}
-
-template
-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
-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 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 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
-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(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(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
-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 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
-void segment_tree<_Key, _Data>::create_leaf_node_instances(const ::std::vector& 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::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
-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 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
-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 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(
- point, m_root_node, result_inserter);
-
- return result;
-}
-
-template
-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(point, m_root_node, result_inserter);
-}
-
-template
-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
-void segment_tree<_Key, _Data>::clear()
-{
- m_tagged_node_map.clear();
- m_segment_data.clear();
- clear_all_nodes();
- m_valid_tree = false;
-}
-
-template
-size_t segment_tree<_Key, _Data>::size() const
-{
- return m_segment_data.size();
-}
-
-template
-bool segment_tree<_Key, _Data>::empty() const
-{
- return m_segment_data.empty();
-}
-
-template
-size_t segment_tree<_Key, _Value>::leaf_size() const
-{
- return __st::count_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
-}
-
-template
-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(p)->value_leaf.data_chain;
- else
- chain = static_cast(p)->value_nonleaf.data_chain;
-
- if (!chain)
- continue;
-
- remove_data_from_chain(*chain, pdata);
- }
-}
-
-template
-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
-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
-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::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
-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
-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
-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
-bool segment_tree<_Key, _Data>::verify_leaf_nodes(const ::std::vector& checks) const
-{
- using namespace std;
-
- node* cur_node = m_left_leaf.get();
- typename ::std::vector::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 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
-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
-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(pnode)->value_leaf.data_chain;
- else
- chain = static_cast(pnode)->value_nonleaf.data_chain;
-
- if (!chain)
- return false;
-
- if (find(chain->begin(), chain->end(), pdata) == chain->end())
- return false;
- }
- return true;
-}
-
-template
-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 -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/include/mdds/segment_tree_def.inl new/mdds_0.12.1/include/mdds/segment_tree_def.inl
--- old/mdds_0.12.0/include/mdds/segment_tree_def.inl 1970-01-01 01:00:00.000000000 +0100
+++ new/mdds_0.12.1/include/mdds/segment_tree_def.inl 2015-06-12 01:53:55.000000000 +0200
@@ -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
+segment_tree<_Key, _Data>::segment_tree()
+ : m_root_node(NULL)
+ , m_valid_tree(false)
+{
+}
+
+template
+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
+segment_tree<_Key, _Data>::~segment_tree()
+{
+ clear_all_nodes();
+}
+
+template
+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
+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 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 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
+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(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(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
+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 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
+void segment_tree<_Key, _Data>::create_leaf_node_instances(const ::std::vector& 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::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
+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 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
+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 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(
+ point, m_root_node, result_inserter);
+
+ return result;
+}
+
+template
+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(point, m_root_node, result_inserter);
+}
+
+template
+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
+void segment_tree<_Key, _Data>::clear()
+{
+ m_tagged_node_map.clear();
+ m_segment_data.clear();
+ clear_all_nodes();
+ m_valid_tree = false;
+}
+
+template
+size_t segment_tree<_Key, _Data>::size() const
+{
+ return m_segment_data.size();
+}
+
+template
+bool segment_tree<_Key, _Data>::empty() const
+{
+ return m_segment_data.empty();
+}
+
+template
+size_t segment_tree<_Key, _Value>::leaf_size() const
+{
+ return __st::count_leaf_nodes(m_left_leaf.get(), m_right_leaf.get());
+}
+
+template
+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(p)->value_leaf.data_chain;
+ else
+ chain = static_cast(p)->value_nonleaf.data_chain;
+
+ if (!chain)
+ continue;
+
+ remove_data_from_chain(*chain, pdata);
+ }
+}
+
+template
+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
+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
+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::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
+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
+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
+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
+bool segment_tree<_Key, _Data>::verify_leaf_nodes(const ::std::vector& checks) const
+{
+ using namespace std;
+
+ node* cur_node = m_left_leaf.get();
+ typename ::std::vector::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 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
+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
+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(pnode)->value_leaf.data_chain;
+ else
+ chain = static_cast(pnode)->value_nonleaf.data_chain;
+
+ if (!chain)
+ return false;
+
+ if (find(chain->begin(), chain->end(), pdata) == chain->end())
+ return false;
+ }
+ return true;
+}
+
+template
+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 -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/mdds_0.12.0/src/flat_segment_tree_test.cpp new/mdds_0.12.1/src/flat_segment_tree_test.cpp
--- old/mdds_0.12.0/src/flat_segment_tree_test.cpp 2015-02-06 03:32:45.000000000 +0100
+++ new/mdds_0.12.1/src/flat_segment_tree_test.cpp 2015-06-12 01:53:55.000000000 +0200
@@ -30,6 +30,7 @@
#include <list>
#include <iostream>
+#include <string>
#include <vector>
#include <limits>
#include <iterator>
@@ -1928,6 +1929,40 @@
assert(!db3.is_tree_valid());
}
+void fst_test_non_numeric_value()
+{
+ stack_printer __stack_printer__("::fst_test_non_numeric_value");
+
+ typedef flat_segment_tree 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 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 @@
fst_test_swap();
fst_test_clear();
fst_test_assignment();
+ fst_test_non_numeric_value();
+ fst_test_non_numeric_key();
}
if (opt.test_perf)