[Boost-commit] svn:boost r50444 - in sandbox/SOC/2006/tree/trunk: boost/tree/detail/comparators libs/tree/doc libs/tree/example libs/tree/test

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"