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 - [email protected] + +- 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 <[email protected]>. # @@ -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='[email protected]' 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, [email protected]) +AC_INIT(mdds, 0.12.1, [email protected]) 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 <boost/intrusive_ptr.hpp> 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<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 -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<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 -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<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 @@ fst_test_swap(); fst_test_clear(); fst_test_assignment(); + fst_test_non_numeric_value(); + fst_test_non_numeric_key(); } if (opt.test_perf)
