Subject: [Boost-commit] svn:boost r68144 - in trunk: boost/detail boost/graph/distributed boost/range/algorithm_ext libs/detail/test
From: admin_at_[hidden]
Date: 2011-01-13 22:02:48
Author: wash
Date: 2011-01-13 22:02:47 EST (Thu, 13 Jan 2011)
New Revision: 68144
URL: http://svn.boost.org/trac/boost/changeset/68144
Log:
Removed the use of __gnu_cxx::is_sorted from Boost.Graph as it's lolnonportable,
implemented a version of the algorithm as a replacement,
Added:
trunk/boost/detail/is_sorted.hpp (contents, props changed)
trunk/libs/detail/test/is_sorted_test.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/distributed/connected_components.hpp | 24 ++++++++++++----------
trunk/boost/range/algorithm_ext/is_sorted.hpp | 42 +++++++++++++--------------------------
2 files changed, 27 insertions(+), 39 deletions(-)
Added: trunk/boost/detail/is_sorted.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/detail/is_sorted.hpp 2011-01-13 22:02:47 EST (Thu, 13 Jan 2011)
@@ -0,0 +1,56 @@
+/*==============================================================================
+ Copyright (c) 2010-2011 Bryce Lelbach
+
+ 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)
+==============================================================================*/
+
+#ifndef BOOST_DETAIL_SORTED_HPP
+#define BOOST_DETAIL_SORTED_HPP
+
+#include <boost/detail/iterator.hpp>
+
+#include <functional>
+
+namespace boost {
+namespace detail {
+
+template<class Iterator, class Comp>
+inline Iterator is_sorted_until (Iterator first, Iterator last, Comp compare) {
+ if (first == last)
+ return last;
+
+ Iterator it = first; ++it;
+
+ for (; it != last; first = it, ++it)
+ if (compare(*it, *first))
+ return it;
+
+ return it;
+}
+
+template<class Iterator>
+inline Iterator is_sorted_until (Iterator first, Iterator last) {
+ typedef typename boost::detail::iterator_traits<Iterator>::value_type
+ value_type;
+
+ typedef std::less<value_type> compare;
+
+ return is_sorted_until(first, last, compare());
+}
+
+template<class Iterator, class Comp>
+inline bool is_sorted (Iterator first, Iterator last, Comp compare) {
+ return is_sorted_until(first, last, compare) == last;
+}
+
+template<class Iterator>
+inline bool is_sorted (Iterator first, Iterator last) {
+ return is_sorted_until(first, last) == last;
+}
+
+} // detail
+} // boost
+
+#endif // BOOST_DETAIL_SORTED_HPP
+
Modified: trunk/boost/graph/distributed/connected_components.hpp
==============================================================================
--- trunk/boost/graph/distributed/connected_components.hpp (original)
+++ trunk/boost/graph/distributed/connected_components.hpp 2011-01-13 22:02:47 EST (Thu, 13 Jan 2011)
@@ -14,6 +14,7 @@
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif
+#include <boost/detail/is_sorted.hpp>
#include <boost/assert.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/parallel/caching_property_map.hpp>
@@ -28,6 +29,7 @@
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/parallel/process_group.hpp>
#include <boost/optional.hpp>
+#include <functional>
#include <algorithm>
#include <vector>
#include <list>
@@ -390,14 +392,14 @@
*aliter = get(p, *aliter);
my_adj.erase
- (remove_if(my_adj.begin(), my_adj.end(),
+ (std::remove_if(my_adj.begin(), my_adj.end(),
cull_adjacency_list<vertex_descriptor,
ParentMap>(*liter, p) ),
my_adj.end());
// This sort needs to be here to make sure the initial
// adjacency list is sorted
- sort(my_adj.begin(), my_adj.end(), std::less<vertex_descriptor>());
- my_adj.erase(unique(my_adj.begin(), my_adj.end()), my_adj.end());
+ std::sort(my_adj.begin(), my_adj.end(), std::less<vertex_descriptor>());
+ my_adj.erase(std::unique(my_adj.begin(), my_adj.end()), my_adj.end());
}
// Get p(v) for the new adjacent roots
@@ -555,10 +557,10 @@
adj[*liter].begin(), adj[*liter].end() );
#ifdef PBGL_IN_PLACE_MERGE
#ifdef PBGL_SORT_ASSERT
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.begin(),
+ BOOST_ASSERT(boost::detail::is_sorted(my_adj.begin(),
my_adj.end() - adj[*liter].size(),
std::less<vertex_descriptor>()));
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.end() - adj[*liter].size(),
+ BOOST_ASSERT(boost::detail::is_sorted(my_adj.end() - adj[*liter].size(),
my_adj.end(),
std::less<vertex_descriptor>()));
#endif
@@ -603,10 +605,10 @@
#ifdef PBGL_IN_PLACE_MERGE
std::size_t num_incoming_edges = incoming_edges.size();
#ifdef PBGL_SORT_ASSERT
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.begin(),
+ BOOST_ASSERT(boost::detail::is_sorted(my_adj.begin(),
my_adj.end() - (num_incoming_edges-1),
std::less<vertex_descriptor>()));
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.end() - (num_incoming_edges-1),
+ BOOST_ASSERT(boost::detail::is_sorted(my_adj.end() - (num_incoming_edges-1),
my_adj.end(),
std::less<vertex_descriptor>()));
#endif
@@ -629,15 +631,15 @@
// the most potential to hook to at each step
std::vector<vertex_descriptor>& my_adj = adj[*liter];
my_adj.erase
- (remove_if(my_adj.begin(), my_adj.end(),
+ (std::remove_if(my_adj.begin(), my_adj.end(),
cull_adjacency_list<vertex_descriptor,
ParentMap>(*liter, p) ),
my_adj.end());
#ifndef PBGL_IN_PLACE_MERGE
- sort(my_adj.begin(), my_adj.end(),
+ std::sort(my_adj.begin(), my_adj.end(),
std::less<vertex_descriptor>() );
#endif
- my_adj.erase(unique(my_adj.begin(), my_adj.end()), my_adj.end());
+ my_adj.erase(std::unique(my_adj.begin(), my_adj.end()), my_adj.end());
}
// Reduce result of empty root list test
@@ -679,7 +681,7 @@
std::vector<vertex_descriptor> my_roots, all_roots;
BGL_FORALL_VERTICES_T(v, g, Graph) {
- if( find( my_roots.begin(), my_roots.end(), get(p, v) )
+ if( std::find( my_roots.begin(), my_roots.end(), get(p, v) )
== my_roots.end() )
my_roots.push_back( get(p, v) );
}
Modified: trunk/boost/range/algorithm_ext/is_sorted.hpp
==============================================================================
--- trunk/boost/range/algorithm_ext/is_sorted.hpp (original)
+++ trunk/boost/range/algorithm_ext/is_sorted.hpp 2011-01-13 22:02:47 EST (Thu, 13 Jan 2011)
@@ -1,3 +1,4 @@
+// Copyright Bryce Lelbach 2010
// Copyright Neil Groves 2009. Use, modification and
// distribution is subject to the Boost Software License, Version
// 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -14,45 +15,26 @@
#include <boost/range/end.hpp>
#include <boost/range/concepts.hpp>
#include <boost/range/value_type.hpp>
+#include <boost/detail/is_sorted.hpp>
#include <algorithm>
namespace boost
{
- namespace range_detail
- {
- template<class ForwardIterator>
- inline bool is_sorted(ForwardIterator first, ForwardIterator last)
- {
- for (ForwardIterator next = first; first != last && ++next != last; ++first)
- if (*next < *first)
- return false;
- return true;
- }
-
- template<class ForwardIterator, class BinaryPredicate>
- inline bool is_sorted(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
- {
- for (ForwardIterator next = first; first != last && ++next != last; ++first)
- if (pred(*next, *first))
- return false;
- return true;
- }
- }
-
namespace range
{
-/// \brief template function count
+/// \brief template function is_sorted
///
-/// range-based version of the count std algorithm
+/// range-based version of the is_sorted std algorithm
///
/// \pre SinglePassRange is a model of the SinglePassRangeConcept
template<class SinglePassRange>
inline bool is_sorted(const SinglePassRange& rng)
{
BOOST_RANGE_CONCEPT_ASSERT((SinglePassRangeConcept<const SinglePassRange>));
- BOOST_RANGE_CONCEPT_ASSERT((LessThanComparableConcept<BOOST_DEDUCED_TYPENAME range_value<const SinglePassRange>::type>));
- return range_detail::is_sorted(boost::begin(rng), boost::end(rng));
+ BOOST_RANGE_CONCEPT_ASSERT((LessThanComparableConcept<BOOST_DEDUCED_TYPENAME
+ range_value<const SinglePassRange>::type>));
+ return boost::detail::is_sorted(boost::begin(rng), boost::end(rng));
}
/// \overload
@@ -60,12 +42,16 @@
inline bool is_sorted(const SinglePassRange& rng, BinaryPredicate pred)
{
BOOST_RANGE_CONCEPT_ASSERT((SinglePassRangeConcept<const SinglePassRange>));
- BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, BOOST_DEDUCED_TYPENAME range_value<const SinglePassRange>::type, BOOST_DEDUCED_TYPENAME range_value<const SinglePassRange>::type>));
- return range_detail::is_sorted(boost::begin(rng), boost::end(rng), pred);
+ BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
+ BOOST_DEDUCED_TYPENAME range_value<const SinglePassRange>::type,
+ BOOST_DEDUCED_TYPENAME range_value<const SinglePassRange>::type>));
+ return boost::detail::is_sorted(boost::begin(rng), boost::end(rng), pred);
}
} // namespace range
- using range::is_sorted;
+
+using range::is_sorted;
+
} // namespace boost
#endif // include guard
Added: trunk/libs/detail/test/is_sorted_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/detail/test/is_sorted_test.cpp 2011-01-13 22:02:47 EST (Thu, 13 Jan 2011)
@@ -0,0 +1,129 @@
+/*==============================================================================
+ Copyright (c) 2010-2011 Bryce Lelbach
+
+ 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 <ios>
+#include <boost/config.hpp>
+#include <boost/array.hpp>
+#include <boost/detail/is_sorted.hpp>
+#include <boost/detail/lightweight_test.hpp>
+
+template<class T>
+struct tracking_less: std::binary_function <T, T, bool> {
+ typedef bool result_type;
+
+ #if defined(__PATHSCALE__)
+ tracking_less (void) { }
+ ~tracking_less (void) { }
+ #endif
+
+ bool operator() (T const& x, T const& y) const {
+ std::cout << x << " < " << y << " == " << (x < y) << "\n";
+ return x < y;
+ }
+};
+
+template<class T>
+struct tracking_less_equal: std::binary_function <T, T, bool> {
+ typedef bool result_type;
+
+ #if defined(__PATHSCALE__)
+ tracking_less_equal (void) { }
+ ~tracking_less_equal (void) { }
+ #endif
+
+ bool operator() (T const& x, T const& y) const {
+ std::cout << x << " <= " << y << " == " << (x <= y) << "\n";
+ return x <= y;
+ }
+};
+
+template<class T>
+struct tracking_greater: std::binary_function <T, T, bool> {
+ typedef bool result_type;
+
+ #if defined(__PATHSCALE__)
+ tracking_greater (void) { }
+ ~tracking_greater (void) { }
+ #endif
+
+ bool operator() (T const& x, T const& y) const {
+ std::cout << x << " > " << y << " == " << (x > y) << "\n";
+ return x > y;
+ }
+};
+
+template<class T>
+struct tracking_greater_equal: std::binary_function <T, T, bool> {
+ typedef bool result_type;
+
+ #if defined(__PATHSCALE__)
+ tracking_greater_equal (void) { }
+ ~tracking_greater_equal (void) { }
+ #endif
+
+ bool operator() (T const& x, T const& y) const {
+ std::cout << x << " >= " << y << " == " << (x >= y) << "\n";
+ return x >= y;
+ }
+};
+
+int main (void) {
+ using boost::detail::is_sorted;
+ using boost::detail::is_sorted_until;
+ using boost::array;
+ using boost::report_errors;
+
+ std::cout << std::boolalpha;
+
+ array<int, 10> a = { { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } };
+ array<int, 10> b = { { 0, 1, 1, 2, 5, 8, 13, 34, 55, 89 } };
+ array<int, 10> c = { { 0, 1, -1, 2, -3, 5, -8, 13, -21, 34 } };
+
+ tracking_less<int> lt;
+ tracking_less_equal<int> lte;
+ tracking_greater<int> gt;
+ tracking_greater_equal<int> gte;
+
+ BOOST_TEST_EQ(is_sorted_until(a.begin(), a.end()), a.end());
+ BOOST_TEST_EQ(is_sorted_until(a.begin(), a.end(), lt), a.end());
+ BOOST_TEST_EQ(is_sorted_until(a.begin(), a.end(), lte), a.end());
+ BOOST_TEST_EQ(*is_sorted_until(a.rbegin(), a.rend(), gt), *a.rend());
+ BOOST_TEST_EQ(*is_sorted_until(a.rbegin(), a.rend(), gte), *a.rend());
+
+ BOOST_TEST_EQ(is_sorted(a.begin(), a.end()), true);
+ BOOST_TEST_EQ(is_sorted(a.begin(), a.end(), lt), true);
+ BOOST_TEST_EQ(is_sorted(a.begin(), a.end(), lte), true);
+ BOOST_TEST_EQ(is_sorted(a.rbegin(), a.rend(), gt), true);
+ BOOST_TEST_EQ(is_sorted(a.rbegin(), a.rend(), gte), true);
+
+ BOOST_TEST_EQ(is_sorted_until(b.begin(), b.end()), b.end());
+ BOOST_TEST_EQ(is_sorted_until(b.begin(), b.end(), lt), b.end());
+ BOOST_TEST_EQ(is_sorted_until(b.begin(), b.end(), lte), &b[2]);
+ BOOST_TEST_EQ(*is_sorted_until(b.rbegin(), b.rend(), gt), *b.rend());
+ BOOST_TEST_EQ(*is_sorted_until(b.rbegin(), b.rend(), gte), b[2]);
+
+ BOOST_TEST_EQ(is_sorted(b.begin(), b.end()), true);
+ BOOST_TEST_EQ(is_sorted(b.begin(), b.end(), lt), true);
+ BOOST_TEST_EQ(is_sorted(b.begin(), b.end(), lte), false);
+ BOOST_TEST_EQ(is_sorted(b.rbegin(), b.rend(), gt), true);
+ BOOST_TEST_EQ(is_sorted(b.rbegin(), b.rend(), gte), false);
+
+ BOOST_TEST_EQ(is_sorted_until(c.begin(), c.end()), &c[2]);
+ BOOST_TEST_EQ(is_sorted_until(c.begin(), c.end(), lt), &c[2]);
+ BOOST_TEST_EQ(is_sorted_until(c.begin(), c.end(), lte), &c[2]);
+ BOOST_TEST_EQ(*is_sorted_until(c.rbegin(), c.rend(), gt), c[7]);
+ BOOST_TEST_EQ(*is_sorted_until(c.rbegin(), c.rend(), gte), c[7]);
+
+ BOOST_TEST_EQ(is_sorted(c.begin(), c.end()), false);
+ BOOST_TEST_EQ(is_sorted(c.begin(), c.end(), lt), false);
+ BOOST_TEST_EQ(is_sorted(c.begin(), c.end(), lte), false);
+ BOOST_TEST_EQ(is_sorted(c.rbegin(), c.rend(), gt), false);
+ BOOST_TEST_EQ(is_sorted(c.rbegin(), c.rend(), gte), false);
+
+ return report_errors();
+}
+