Subject: [Boost-commit] svn:boost r60611 - in trunk/boost: graph/detail pending
From: asutton_at_[hidden]
Date: 2010-03-15 07:22:16
Author: asutton
Date: 2010-03-15 07:22:16 EDT (Mon, 15 Mar 2010)
New Revision: 60611
URL: http://svn.boost.org/trac/boost/changeset/60611
Log:
Addressing #3816. Moved array_binary tree to top-level boost namespace,
which seems to be where most basic data structures. The change introduces
no name collisions, since its only user is mutable_queue. This change
deprecates the use of adstl::array_binary_tree for all users.
Text files modified:
trunk/boost/graph/detail/array_binary_tree.hpp | 61 +++++++++++++++++++--------------------
trunk/boost/pending/mutable_queue.hpp | 28 +++++++++---------
2 files changed, 44 insertions(+), 45 deletions(-)
Modified: trunk/boost/graph/detail/array_binary_tree.hpp
==============================================================================
--- trunk/boost/graph/detail/array_binary_tree.hpp (original)
+++ trunk/boost/graph/detail/array_binary_tree.hpp 2010-03-15 07:22:16 EDT (Mon, 15 Mar 2010)
@@ -8,18 +8,18 @@
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//
-#ifndef ADSTL_ARRAY_BINARY_TREE_HPP
-#define ADSTL_ARRAY_BINARY_TREE_HPP
+#ifndef BOOST_ARRAY_BINARY_TREE_HPP
+#define BOOST_ARRAY_BINARY_TREE_HPP
#include <iterator>
#include <functional>
#include <boost/config.hpp>
-namespace adstl {
- /*
- Note: array_binary_tree is a completey balanced binary tree
- */
+namespace boost {
+/*
+ * Note: array_binary_tree is a completey balanced binary tree.
+ */
#if !defined BOOST_NO_STD_ITERATOR_TRAITS
template <class RandomAccessIterator, class ID>
#else
@@ -45,18 +45,18 @@
: boost::iterator<std::bidirectional_iterator_tag, ArrayBinaryTreeNode,
difference_type, array_binary_tree_node*, ArrayBinaryTreeNode&>
{ // replace with iterator_adaptor implementation -JGS
-
+
inline iterator() : i(0), n(0) { }
inline iterator(const iterator& x) : r(x.r), i(x.i), n(x.n), id(x.id) { }
inline iterator& operator=(const iterator& x) {
- r = x.r; i = x.i; n = x.n;
+ r = x.r; i = x.i; n = x.n;
/*egcs generate a warning*/
- id = x.id;
+ id = x.id;
return *this;
}
- inline iterator(rep_iterator rr,
- size_type ii,
- size_type nn,
+ inline iterator(rep_iterator rr,
+ size_type ii,
+ size_type nn,
const ID& _id) : r(rr), i(ii), n(nn), id(_id) { }
inline array_binary_tree_node operator*() {
return ArrayBinaryTreeNode(r, i, n, id); }
@@ -64,7 +64,7 @@
inline iterator operator++(int)
{ iterator t = *this; ++(*this); return t; }
inline bool operator==(const iterator& x) const { return i == x.i; }
- inline bool operator!=(const iterator& x) const
+ inline bool operator!=(const iterator& x) const
{ return !(*this == x); }
rep_iterator r;
size_type i;
@@ -75,13 +75,13 @@
inline children_type(const children_type& x)
: r(x.r), i(x.i), n(x.n), id(x.id) { }
inline children_type& operator=(const children_type& x) {
- r = x.r; i = x.i; n = x.n;
+ r = x.r; i = x.i; n = x.n;
/*egcs generate a warning*/
- id = x.id;
+ id = x.id;
return *this;
}
inline children_type(rep_iterator rr,
- size_type ii,
+ size_type ii,
size_type nn,
const ID& _id) : r(rr), i(ii), n(nn), id(_id) { }
inline iterator begin() { return iterator(r, 2 * i + 1, n, id); }
@@ -100,23 +100,23 @@
ID id;
};
inline array_binary_tree_node() : i(0), n(0) { }
- inline array_binary_tree_node(const array_binary_tree_node& x)
+ inline array_binary_tree_node(const array_binary_tree_node& x)
: r(x.r), i(x.i), n(x.n), id(x.id) { }
inline ArrayBinaryTreeNode& operator=(const ArrayBinaryTreeNode& x) {
r = x.r;
- i = x.i;
- n = x.n;
+ i = x.i;
+ n = x.n;
/*egcs generate a warning*/
- id = x.id;
+ id = x.id;
return *this;
}
- inline array_binary_tree_node(rep_iterator start,
- rep_iterator end,
+ inline array_binary_tree_node(rep_iterator start,
+ rep_iterator end,
rep_iterator pos, const ID& _id)
: r(start), i(pos - start), n(end - start), id(_id) { }
- inline array_binary_tree_node(rep_iterator rr,
- size_type ii,
- size_type nn, const ID& _id)
+ inline array_binary_tree_node(rep_iterator rr,
+ size_type ii,
+ size_type nn, const ID& _id)
: r(rr), i(ii), n(nn), id(_id) { }
inline value_type& value() { return *(r + i); }
inline const value_type& value() const { return *(r + i); }
@@ -147,8 +147,8 @@
value() = tmp;
i = x.i;
}
- inline const children_type children() const {
- return children_type(r, i, n);
+ inline const children_type children() const {
+ return children_type(r, i, n);
}
inline size_type index() const { return i; }
rep_iterator r;
@@ -157,7 +157,7 @@
ID id;
};
-template <class RandomAccessContainer,
+template <class RandomAccessContainer,
class Compare = std::less<typename RandomAccessContainer::value_type> >
struct compare_array_node {
typedef typename RandomAccessContainer::value_type value_type;
@@ -176,7 +176,6 @@
Compare comp;
};
+} // namespace boost
-} /* namespace adstl */
-
-#endif /* ADSTL_ARRAY_BINARY_TREE_H */
+#endif /* BOOST_ARRAY_BINARY_TREE_HPP */
Modified: trunk/boost/pending/mutable_queue.hpp
==============================================================================
--- trunk/boost/pending/mutable_queue.hpp (original)
+++ trunk/boost/pending/mutable_queue.hpp 2010-03-15 07:22:16 EDT (Mon, 15 Mar 2010)
@@ -23,20 +23,20 @@
namespace boost {
// The mutable queue whose elements are indexed
- //
+ //
// This adaptor provides a special kind of priority queue that has
// and update operation. This allows the ordering of the items to
// change. After the ordering criteria for item x changes, one must
// call the Q.update(x)
- //
+ //
// In order to efficiently find x in the queue, a functor must be
// provided to map value_type to a unique ID, which the
// mutable_queue will then use to map to the location of the
// item. The ID's generated must be between 0 and N, where N is the
// value passed to the constructor of mutable_queue
- template <class IndexedType,
- class RandomAccessContainer = std::vector<IndexedType>,
+ template <class IndexedType,
+ class RandomAccessContainer = std::vector<IndexedType>,
class Comp = std::less<typename RandomAccessContainer::value_type>,
class ID = identity_property_map >
class mutable_queue {
@@ -46,23 +46,23 @@
protected:
typedef typename RandomAccessContainer::iterator iterator;
#if !defined BOOST_NO_STD_ITERATOR_TRAITS
- typedef adstl::array_binary_tree_node<iterator, ID> Node;
+ typedef array_binary_tree_node<iterator, ID> Node;
#else
- typedef adstl::array_binary_tree_node<iterator, value_type, ID> Node;
+ typedef array_binary_tree_node<iterator, value_type, ID> Node;
#endif
- typedef adstl::compare_array_node<RandomAccessContainer,Comp> Compare;
+ typedef compare_array_node<RandomAccessContainer,Comp> Compare;
typedef std::vector<size_type> IndexArray;
public:
typedef Compare value_compare;
typedef ID id_generator;
- mutable_queue(size_type n, const Comp& x, const ID& _id)
+ mutable_queue(size_type n, const Comp& x, const ID& _id)
: index_array(n), comp(x), id(_id) {
- c.reserve(n);
+ c.reserve(n);
}
template <class ForwardIterator>
- mutable_queue(ForwardIterator first, ForwardIterator last,
- const Comp& x, const ID& _id)
+ mutable_queue(ForwardIterator first, ForwardIterator last,
+ const Comp& x, const ID& _id)
: index_array(std::distance(first, last)), comp(x), id(_id)
{
while( first != last ) {
@@ -72,7 +72,7 @@
}
bool empty() const { return c.empty(); }
-
+
void pop() {
value_type tmp = c.back();
c.back() = c.front();
@@ -86,7 +86,7 @@
c.pop_back();
Node node(c.begin(), c.end(), c.begin(), id);
- down_heap(node, comp, index_array);
+ down_heap(node, comp, index_array);
}
void push(const IndexedType& x) {
c.push_back(x);
@@ -120,7 +120,7 @@
bool test() {
return std::is_heap(c.begin(), c.end(), Comp());
}
-#endif
+#endif
protected:
IndexArray index_array;