Subject: [Boost-commit] svn:boost r50444 - in sandbox/SOC/2006/tree/trunk: boost/tree/detail/comparators libs/tree/doc libs/tree/example libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-02 14:49:40
Author: bernhard.reiter
Date: 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
New Revision: 50444
URL: http://svn.boost.org/trac/boost/changeset/50444
Log:
Continue detail directory re-organization.
Added:
sandbox/SOC/2006/tree/trunk/libs/tree/example/interval_search_binary_tree.FIXMEcpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/libs/tree/example/string_comparator.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/libs/tree/example/string_search_binary_tree.FIXMEcpp (contents, props changed)
Removed:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/comparators/
sandbox/SOC/2006/tree/trunk/libs/tree/test/interval_search_binary_tree_test.cpp
sandbox/SOC/2006/tree/trunk/libs/tree/test/search_ordered_vector_test.cpp
sandbox/SOC/2006/tree/trunk/libs/tree/test/string_search_binary_tree_test.cpp
Text files modified:
sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2 | 7 -------
sandbox/SOC/2006/tree/trunk/libs/tree/doc/algorithms.qbk | 4 ++--
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 4 ----
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 2 +-
4 files changed, 3 insertions(+), 14 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
@@ -15,15 +15,8 @@
doxygen autodoc
:
[ glob ../../../boost/tree/*.hpp ]
- [ glob ../../../boost/tree/detail/algorithm/*.hpp ]
- [ glob ../../../boost/tree/detail/algorithm/cursor/*.hpp ]
- [ glob ../../../boost/tree/detail/algorithm/iterator/*.hpp ]
[ glob ../../../boost/tree/detail/augmentors/*.hpp ]
[ glob ../../../boost/tree/detail/balancers/*.hpp ]
- [ glob ../../../boost/tree/detail/comparators/*.hpp ]
- [ glob ../../../boost/tree/detail/cursor/*.hpp ]
- [ glob ../../../boost/tree/detail/iterator/*.hpp ]
- [ glob ../../../boost/tree/detail/node/*.hpp ]
:
<doxygen:param>"PREDEFINED=\"BOOST_PROCESS_DOXYGEN\""
<xsl:param>boost.doxygen.detailns=documenteverything
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/algorithms.qbk
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/algorithms.qbk (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/algorithms.qbk 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
@@ -12,8 +12,8 @@
/]
[import ../../../boost/tree/algorithm.hpp]
-[import ../../../boost/tree/detail/algorithm/general.hpp]
-[import ../../../boost/tree/detail/algorithm/inorder.hpp]
+[import ../../../boost/tree/general_algorithms.hpp]
+[import ../../../boost/tree/inorder_algorithms.hpp]
[import ../example/for_each.cpp]
[section Algorithms]
Added: sandbox/SOC/2006/tree/trunk/libs/tree/example/interval_search_binary_tree.FIXMEcpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/example/interval_search_binary_tree.FIXMEcpp 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,62 @@
+// Copyright (c) 2006-2009, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/tree/binary_tree.hpp>
+#include <boost/tree/searcher.hpp>
+
+#include <boost/numeric/interval.hpp>
+//#include <boost/numeric/interval/compare/lexicographic.hpp>
+#include <boost/multi_index/identity.hpp>
+
+#define BOOST_TEST_MODULE interval_search test
+//#define BOOST_TEST_DYN_LINK
+#include <boost/test/included/unit_test.hpp>
+
+//TODO: add real tests. (what is where?)
+// test overlaps stuff.
+
+// Interval example data as in GCC libstdc++'s pb_ds
+
+// FIXME: Still buggy.
+// Is the following really what we want?
+using namespace boost::numeric::interval_lib::compare::lexicographic;
+using boost::numeric::interval_lib::cerlt;
+using boost::numeric::interval;
+
+template <typename T>
+struct cerless {
+ inline bool operator() (T const& a, T const& b)
+ {
+ return boost::numeric::interval_lib::cerlt(a,b);
+ }
+};
+
+BOOST_AUTO_TEST_CASE( interval_search_binary_tree_test )
+{
+ using boost::tree::searcher;
+ using boost::tree::binary_tree;
+
+ using boost::multi_index::identity;
+
+ typedef searcher<false, binary_tree<interval<int> >, identity<interval<int> >,
+ cerless<interval<int> > > searcher_t;
+ searcher_t my_tree;
+
+ my_tree.insert(interval<int>(20,36));
+ my_tree.insert(interval<int>( 3,41));
+ my_tree.insert(interval<int>(10,15));
+ my_tree.insert(interval<int>( 0, 1));
+ my_tree.insert(interval<int>(29,99));
+
+ searcher_t::iterator ci = my_tree.begin();
+ BOOST_CHECK_EQUAL(*ci++, interval<int>( 0, 1));
+// BOOST_CHECK_EQUAL(*ci++, interval<int>( 3,41));
+ BOOST_CHECK_EQUAL(*ci++, interval<int>(10,15));
+// BOOST_CHECK_EQUAL(*ci++, interval<int>(20,36));
+// BOOST_CHECK_EQUAL(*ci++, interval<int>(29,99));
+// BOOST_CHECK_EQUAL(ci, my_tree.end());
+
+}
Added: sandbox/SOC/2006/tree/trunk/libs/tree/example/string_comparator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/example/string_comparator.hpp 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,48 @@
+// Copyright (c) 2006-2009, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+/**
+ * @file string.hpp
+ * Optimising string comparator
+ */
+
+#ifndef BOOST_TREE_COMPARATORS_STRING_HPP
+#define BOOST_TREE_COMPARATORS_STRING_HPP
+
+#include <algorithm>
+
+namespace boost {
+namespace tree {
+
+//concept check Cntnr1::value_type == Cntnr2::value_type
+//ditto for size_type
+//ForwardContainer? (cause we need quick positioning with size_type...)
+template <class Cntnr1, class Cntnr2>
+class container_lexicographical_compare : public std::binary_function<Cntnr1, Cntnr2, bool> {
+public:
+ container_lexicographical_compare(typename Cntnr1::size_type pos = 0) : m_pos(pos) {}
+ bool operator() (Cntnr1 const& x, Cntnr2 const& y)
+ {
+ typename Cntnr1::const_iterator it1 = x.begin();
+ typename Cntnr2::const_iterator it2 = y.begin();
+ std::advance(it1, m_pos);
+ std::advance(it2, m_pos);
+ bool ret = std::lexicographical_compare(it1, x.end(), it2, y.end());
+ m_pos = std::distance(x.begin(), it1);
+ return ret;
+ }
+private:
+ typename Cntnr1::size_type m_pos;
+};
+
+//TODO: even more efficient version for strings (using their compare members)
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_COMPARATORS_STRING_HPP
+
+
Added: sandbox/SOC/2006/tree/trunk/libs/tree/example/string_search_binary_tree.FIXMEcpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/example/string_search_binary_tree.FIXMEcpp 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,85 @@
+// Copyright (c) 2006-2009, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/tree/binary_tree.hpp>
+#include <boost/tree/balanced_tree.hpp>
+#include <boost/tree/searcher.hpp>
+
+#include <boost/tree/balancers/unbalanced.hpp>
+
+#include <boost/multi_index/identity.hpp>
+
+#include "string_comparator.hpp"
+
+#include <string>
+
+#define BOOST_TEST_MODULE string_search test
+//#define BOOST_TEST_DYN_LINK
+#include <boost/test/included/unit_test.hpp>
+
+//Words from Austern et al., p1290
+
+//TODO: add real tests. (what is where?)
+//does boost have timers? what does the austern et al one look like?
+// TODO: get timings. that makes that no testcase anymore, right?
+void test_normal_string_search_binary_tree()
+{
+ using namespace boost::tree;
+
+ typedef searcher<false, balanced_tree<binary_tree<std::string>, balancers::unbalanced > > searcher_t;
+ searcher_t my_tree;
+
+ my_tree.insert("anthology");
+ my_tree.insert("anagram");
+ my_tree.insert("anodyne");
+ my_tree.insert("anthrax");
+ my_tree.insert("anteater");
+
+ //FIXME: const_iterator doesn't work properly yet
+ searcher_t::iterator ci = my_tree.begin();
+ BOOST_CHECK_EQUAL(*ci++, "anagram");
+ BOOST_CHECK_EQUAL(*ci++, "anodyne");
+ BOOST_CHECK_EQUAL(*ci++, "anteater");
+ BOOST_CHECK_EQUAL(*ci++, "anthology");
+ BOOST_CHECK_EQUAL(*ci++, "anthrax");
+ BOOST_CHECK_EQUAL(ci, my_tree.end());
+}
+
+void test_optimized_string_search_binary_tree()
+{
+
+ using namespace boost::tree;
+ using boost::multi_index::identity;
+
+ typedef searcher<false, balanced_tree<binary_tree<std::string>, balancers::unbalanced>,
+ identity<std::string>,
+ container_lexicographical_compare<std::string, std::string>
+ > searcher_t;
+ searcher_t my_tree;
+
+ my_tree.insert("anthology");
+ my_tree.insert("anagram");
+ my_tree.insert("anodyne");
+ my_tree.insert("anthrax");
+ my_tree.insert("anteater");
+
+ //FIXME: const_iterator doesn't work properly yet
+ searcher_t::iterator ci = my_tree.begin();
+ BOOST_CHECK_EQUAL(*ci++, "anagram");
+ BOOST_CHECK_EQUAL(*ci++, "anodyne");
+ BOOST_CHECK_EQUAL(*ci++, "anteater");
+ BOOST_CHECK_EQUAL(*ci++, "anthology");
+ BOOST_CHECK_EQUAL(*ci++, "anthrax");
+ BOOST_CHECK_EQUAL(ci, my_tree.end());
+}
+
+
+BOOST_AUTO_TEST_CASE( string_search_binary_tree_test )
+{
+ test_normal_string_search_binary_tree();
+ test_optimized_string_search_binary_tree();
+ return 0;
+}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
@@ -40,10 +40,6 @@
[ run algorithm_concepts_test.cpp ]
[ run cursor_algorithm_test.cpp ]
[ run iterator_algorithm_test.cpp ]
-# [ run string_search_binary_tree_test.cpp ]
-# [ run flat_forest_tree_test.cpp ]
-# [ run interval_search_binary_tree_test.cpp ]
-# [ run search_ordered_vector_test.cpp ]
# [ run red_black_tree_test.cpp ]
# [ run treap_test.cpp ]
[ run forest_tree_test.cpp ]
Deleted: sandbox/SOC/2006/tree/trunk/libs/tree/test/interval_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/interval_search_binary_tree_test.cpp 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
+++ (empty file)
@@ -1,62 +0,0 @@
-// Copyright (c) 2006-2009, Bernhard Reiter
-//
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/searcher.hpp>
-
-#include <boost/numeric/interval.hpp>
-//#include <boost/numeric/interval/compare/lexicographic.hpp>
-#include <boost/multi_index/identity.hpp>
-
-#define BOOST_TEST_MODULE interval_search test
-//#define BOOST_TEST_DYN_LINK
-#include <boost/test/included/unit_test.hpp>
-
-//TODO: add real tests. (what is where?)
-// test overlaps stuff.
-
-// Interval example data as in GCC libstdc++'s pb_ds
-
-// FIXME: Still buggy.
-// Is the following really what we want?
-using namespace boost::numeric::interval_lib::compare::lexicographic;
-using boost::numeric::interval_lib::cerlt;
-using boost::numeric::interval;
-
-template <typename T>
-struct cerless {
- inline bool operator() (T const& a, T const& b)
- {
- return boost::numeric::interval_lib::cerlt(a,b);
- }
-};
-
-BOOST_AUTO_TEST_CASE( interval_search_binary_tree_test )
-{
- using boost::tree::searcher;
- using boost::tree::binary_tree;
-
- using boost::multi_index::identity;
-
- typedef searcher<false, binary_tree<interval<int> >, identity<interval<int> >,
- cerless<interval<int> > > searcher_t;
- searcher_t my_tree;
-
- my_tree.insert(interval<int>(20,36));
- my_tree.insert(interval<int>( 3,41));
- my_tree.insert(interval<int>(10,15));
- my_tree.insert(interval<int>( 0, 1));
- my_tree.insert(interval<int>(29,99));
-
- searcher_t::iterator ci = my_tree.begin();
- BOOST_CHECK_EQUAL(*ci++, interval<int>( 0, 1));
-// BOOST_CHECK_EQUAL(*ci++, interval<int>( 3,41));
- BOOST_CHECK_EQUAL(*ci++, interval<int>(10,15));
-// BOOST_CHECK_EQUAL(*ci++, interval<int>(20,36));
-// BOOST_CHECK_EQUAL(*ci++, interval<int>(29,99));
-// BOOST_CHECK_EQUAL(ci, my_tree.end());
-
-}
Deleted: sandbox/SOC/2006/tree/trunk/libs/tree/test/search_ordered_vector_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/search_ordered_vector_test.cpp 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
+++ (empty file)
@@ -1,49 +0,0 @@
-// Copyright (c) 2006-2009, Bernhard Reiter
-//
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#include <boost/tree/searcher.hpp>
-
-#include <vector>
-
-#define BOOST_TEST_MODULE search_ordered_vector test
-//#define BOOST_TEST_DYN_LINK
-#include <boost/test/included/unit_test.hpp>
-
-BOOST_AUTO_TEST_CASE( search_ordered_vector_test )
-{
-// using boost::tree::searcher;
-// using std::vector;
-//
-// typedef searcher<false, vector<int> > searcher_t;
-// searcher_t my_searcher;
-//
-// searcher_t::cursor c, c1, c2, c3, c4, c5;
-//
-// c = my_searcher.end();
-//
-// c1 = my_searcher.insert(c, 18);
-// c1 = my_searcher.insert(c1, 7); //FIXME: crash if pos hint == c
-// c1 = my_searcher.insert(c1, 6);
-// c1 = my_searcher.insert(c1, 8);
-//
-// c1 = my_searcher.begin();
-// BOOST_CHECK_EQUAL(*c1++, 6);
-// BOOST_CHECK_EQUAL(*c1++, 7);
-// BOOST_CHECK_EQUAL(*c1++, 8);
-// BOOST_CHECK_EQUAL(*c1++, 18);
-// BOOST_CHECK_EQUAL(c1, my_searcher.end());
-}
-
-//boost::unit_test::test_suite*
-//init_unit_test_suite( int argc, char* argv[] )
-//{
-// boost::unit_test::test_suite* ordered_vector_test =
-// BOOST_TEST_SUITE( "Ordered vector test" );
-//
-// ordered_vector_test->add( BOOST_TEST_CASE( &search_ordered_vector_test ) );
-//
-// return ordered_vector_test;
-//}
\ No newline at end of file
Deleted: sandbox/SOC/2006/tree/trunk/libs/tree/test/string_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/string_search_binary_tree_test.cpp 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
+++ (empty file)
@@ -1,85 +0,0 @@
-// Copyright (c) 2006-2009, Bernhard Reiter
-//
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/balanced_tree.hpp>
-#include <boost/tree/searcher.hpp>
-
-#include <boost/tree/balancers/unbalanced.hpp>
-
-#include <boost/tree/comparators/string.hpp>
-
-#include <boost/multi_index/identity.hpp>
-
-#include <string>
-
-#define BOOST_TEST_MODULE string_search test
-//#define BOOST_TEST_DYN_LINK
-#include <boost/test/included/unit_test.hpp>
-
-//Words from Austern et al., p1290
-
-//TODO: add real tests. (what is where?)
-//does boost have timers? what does the austern et al one look like?
-// TODO: get timings. that makes that no testcase anymore, right?
-void test_normal_string_search_binary_tree()
-{
- using namespace boost::tree;
-
- typedef searcher<false, balanced_tree<binary_tree<std::string>, balancers::unbalanced > > searcher_t;
- searcher_t my_tree;
-
- my_tree.insert("anthology");
- my_tree.insert("anagram");
- my_tree.insert("anodyne");
- my_tree.insert("anthrax");
- my_tree.insert("anteater");
-
- //FIXME: const_iterator doesn't work properly yet
- searcher_t::iterator ci = my_tree.begin();
- BOOST_CHECK_EQUAL(*ci++, "anagram");
- BOOST_CHECK_EQUAL(*ci++, "anodyne");
- BOOST_CHECK_EQUAL(*ci++, "anteater");
- BOOST_CHECK_EQUAL(*ci++, "anthology");
- BOOST_CHECK_EQUAL(*ci++, "anthrax");
- BOOST_CHECK_EQUAL(ci, my_tree.end());
-}
-
-void test_optimized_string_search_binary_tree()
-{
-
- using namespace boost::tree;
- using boost::multi_index::identity;
-
- typedef searcher<false, balanced_tree<binary_tree<std::string>, balancers::unbalanced>,
- identity<std::string>,
- container_lexicographical_compare<std::string, std::string>
- > searcher_t;
- searcher_t my_tree;
-
- my_tree.insert("anthology");
- my_tree.insert("anagram");
- my_tree.insert("anodyne");
- my_tree.insert("anthrax");
- my_tree.insert("anteater");
-
- //FIXME: const_iterator doesn't work properly yet
- searcher_t::iterator ci = my_tree.begin();
- BOOST_CHECK_EQUAL(*ci++, "anagram");
- BOOST_CHECK_EQUAL(*ci++, "anodyne");
- BOOST_CHECK_EQUAL(*ci++, "anteater");
- BOOST_CHECK_EQUAL(*ci++, "anthology");
- BOOST_CHECK_EQUAL(*ci++, "anthrax");
- BOOST_CHECK_EQUAL(ci, my_tree.end());
-}
-
-
-BOOST_AUTO_TEST_CASE( string_search_binary_tree_test )
-{
- test_normal_string_search_binary_tree();
- test_optimized_string_search_binary_tree();
- return 0;
-}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp 2009-01-02 14:49:39 EST (Fri, 02 Jan 2009)
@@ -10,7 +10,7 @@
#include <boost/tree/binary_tree.hpp>
#include <boost/tree/algorithm.hpp>
-#include <list>
+#include <vector>
#include "helpers.hpp"