Subject: [Boost-commit] svn:boost r50600 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-14 16:59:51
Author: bernhard.reiter
Date: 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
New Revision: 50600
URL: http://svn.boost.org/trac/boost/changeset/50600
Log:
Rename balanced_tree -> balance
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp
- copied, changed from r50443, /sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
Removed:
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp | 98 ++++++++++++++++++++--------------------
sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp | 4
6 files changed, 58 insertions(+), 58 deletions(-)
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp (from r50443, /sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
@@ -5,13 +5,13 @@
// http://www.boost.org/LICENSE_1_0.txt)
/**
- * @file balanced_tree.hpp
+ * @file balance.hpp
* Balanced tree implementation
*/
-#ifndef BOOST_TREE_BALANCED_TREE_HPP
-#define BOOST_TREE_BALANCED_TREE_HPP
+#ifndef BOOST_TREE_balance_HPP
+#define BOOST_TREE_balance_HPP
#include <boost/tree/cursor.hpp>
#include <boost/tree/iterator.hpp>
@@ -150,13 +150,13 @@
}
template <class Cursor>
-class balanced_tree_iterator
+class balance_iterator
: public iterator<inorder, is_on_top_cursor<Cursor> > {
public:
- balanced_tree_iterator()
+ balance_iterator()
: iterator<inorder, is_on_top_cursor<Cursor> >() {}
- explicit balanced_tree_iterator(Cursor p)
+ explicit balance_iterator(Cursor p)
: iterator<inorder, is_on_top_cursor<Cursor> >(p) {}
operator Cursor()
@@ -166,13 +166,13 @@
};
/**
- * @brief A %balanced_tree.
+ * @brief A %balance.
* This class models the hierarchy concept, the container concept and the
* sequence concept. TODO: complete this...
*
*/
template <class Hierarchy, class Balance>
-class balanced_tree {
+class balance {
public:
typedef typename Hierarchy::value_type value_type;
typedef Balance balancer_type;
@@ -187,14 +187,14 @@
hierarchy_type h;
private:
- typedef balanced_tree<Hierarchy, Balance> self_type;
+ typedef balance<Hierarchy, Balance> self_type;
typedef typename hierarchy_type::cursor cursor;
typedef typename hierarchy_type::const_cursor const_cursor;
public:
- typedef augmented_iterator<balanced_tree_iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
- typedef augmented_iterator<balanced_tree_iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
+ typedef augmented_iterator<balance_iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
+ typedef augmented_iterator<balance_iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
@@ -205,18 +205,18 @@
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
- explicit balanced_tree (hierarchy_type const& hier = hierarchy_type())
+ explicit balance (hierarchy_type const& hier = hierarchy_type())
: h(hier)
{}
// TODO: 3rd arg...?
- explicit balanced_tree (size_type n, value_type const& value = value_type(),
+ explicit balance (size_type n, value_type const& value = value_type(),
hierarchy_type const& hier = hierarchy_type())
: h(hier)
{}
template <class InputIterator>
- balanced_tree (InputIterator first, InputIterator last,
+ balance (InputIterator first, InputIterator last,
hierarchy_type const& hier = hierarchy_type())
: h(hier)
{
@@ -224,7 +224,7 @@
this->insert(this->end(), *first);
}
- balanced_tree (self_type const& other)
+ balance (self_type const& other)
: h(other.h)
{}
@@ -265,7 +265,7 @@
/**
* Returns a read/write ("mutable") inorder iterator to the position one
- * past the last (inorder) value in the %balanced_tree.
+ * past the last (inorder) value in the %balance.
*/
iterator end()
{
@@ -274,7 +274,7 @@
/**
* Returns a read-only inorder const_iterator to the position one past the
- * last (inorder) value in the %balanced_tree.
+ * last (inorder) value in the %balance.
*/
const_iterator end() const
{
@@ -283,7 +283,7 @@
/**
* Returns a read-only inorder const_iterator to the position one past the
- * last (inorder) value in the %balanced_tree.
+ * last (inorder) value in the %balance.
*/
const_iterator cend() const
{
@@ -291,12 +291,12 @@
}
/**
- * @brief Finds the first position in the @balanced_tree in which @a k
+ * @brief Finds the first position in the @balance in which @a k
* could be inserted without changing the ordering, using <
* (less than) for comparisons.
* @param k The search term
* @return An iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
+ * @a k, or end() if every element in the @balance is
* less than @a k.
*/
iterator lower_bound(value_type const& k)
@@ -305,12 +305,12 @@
}
/**
- * @brief Finds the first position in the @balanced_tree in which @a k
+ * @brief Finds the first position in the @balance in which @a k
* could be inserted without changing the ordering, using <
* (less than) for comparisons.
* @param k The search term
* @return A const_iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
+ * @a k, or end() if every element in the @balance is
* less than @a k.
*/
const_iterator lower_bound(value_type const& k) const
@@ -319,13 +319,13 @@
}
/**
- * @brief Finds the first position in the @balanced_tree in which @a k
+ * @brief Finds the first position in the @balance in which @a k
* could be inserted without changing the ordering, using cmp
* for comparisons.
* @param k The search term
* @param cmp The comparison functor
* @return An iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
+ * @a k, or end() if every element in the @balance is
* less than @a k.
*/
template <class Cmp>
@@ -336,13 +336,13 @@
}
/**
- * @brief Finds the first position in the @balanced_tree in which @a k
+ * @brief Finds the first position in the @balance in which @a k
* could be inserted without changing the ordering, using cmp
* for comparisons.
* @param k The search term
* @param cmp The comparison functor
* @return A const_iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
+ * @a k, or end() if every element in the @balance is
* less than @a k.
*/
template <class Cmp>
@@ -353,12 +353,12 @@
}
/**
- * @brief Finds the last position in the @balanced_tree in which @a k
+ * @brief Finds the last position in the @balance in which @a k
* could be inserted without changing the ordering, using <
* (less than) for comparisons.
* @param k The search term
* @return An iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
+ * @a k, or end() if no element in the @balance is
* greater than @a k.
*/
iterator upper_bound(value_type const& k)
@@ -367,12 +367,12 @@
}
/**
- * @brief Finds the last position in the @balanced_tree in which @a k
+ * @brief Finds the last position in the @balance in which @a k
* could be inserted without changing the ordering, using <
* (less than) for comparisons.
* @param k The search term
* @return A const_iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
+ * @a k, or end() if no element in the @balance is
* greater than @a k.
*/
const_iterator upper_bound(value_type const& k) const
@@ -381,13 +381,13 @@
}
/**
- * @brief Finds the last position in the @balanced_tree in which @a k
+ * @brief Finds the last position in the @balance in which @a k
* could be inserted without changing the ordering, using cmp
* for comparisons.
* @param k The search term
* @param cmp The comparison functor
* @return An iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
+ * @a k, or end() if no element in the @balance is
* greater than @a k.
*/
template <class Cmp>
@@ -398,13 +398,13 @@
}
/**
- * @brief Finds the last position in the @balanced_tree in which @a k
+ * @brief Finds the last position in the @balance in which @a k
* could be inserted without changing the ordering, using cmp
* for comparisons.
* @param k The search term
* @param cmp The comparison functor
* @return A const_iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
+ * @a k, or end() if no element in the @balance is
* greater than @a k.
*/
template <class Cmp>
@@ -415,12 +415,12 @@
}
/**
- * @brief Add data to the front of the %balanced_tree.
+ * @brief Add data to the front of the %balance.
* @param x Data to be added.
*
* This is a typical stack operation. The function creates an
- * element at the front of the %balanced_tree and assigns the given data to
- * it. Due to the nature of a %balanced_tree this operation can be done
+ * element at the front of the %balance and assigns the given data to
+ * it. Due to the nature of a %balance this operation can be done
* in constant time, and does not invalidate iterators and references.
*/
void push_front(value_type const& x)
@@ -432,7 +432,7 @@
* @brief Removes first element.
*
* This is a typical stack operation. It shrinks the %balance_tree by
- * one. Due to the nature of a %balanced_tree this operation can be done
+ * one. Due to the nature of a %balance this operation can be done
* in constant time, and only invalidates iterators/references to
* the element being removed.
*
@@ -445,12 +445,12 @@
}
/**
- * @brief Add data to the end of the %balanced_tree.
+ * @brief Add data to the end of the %balance.
* @param x Data to be added.
*
* This is a typical stack operation. The function creates an
- * element at the end of the %balanced_tree and assigns the given data to
- * it. Due to the nature of a %balanced_tree this operation can be done
+ * element at the end of the %balance and assigns the given data to
+ * it. Due to the nature of a %balance this operation can be done
* in constant time, and does not invalidate iterators and references.
*/
void push_back(value_type const& x)
@@ -462,7 +462,7 @@
* @brief Removes last element.
*
* This is a typical stack operation. It shrinks the %balance_tree by
- * one. Due to the nature of a %balanced_tree this operation can be done
+ * one. Due to the nature of a %balance this operation can be done
* in constant time, and only invalidates iterators/references to
* the element being removed.
*
@@ -475,7 +475,7 @@
/**
* @brief Inserts val in front of @a pos.
- * @param pos The %balanced_tree iterator in front of which to insert.
+ * @param pos The %balance iterator in front of which to insert.
* @param val The value to insert.
* @return An inorder iterator that points to the inserted data.
*/
@@ -508,9 +508,9 @@
* @return An iterator pointing to the next element (or end()).
*
* This function will erase the element at the given position and thus
- * shorten the %balanced_tree by one.
+ * shorten the %balance by one.
*
- * Due to the nature of a %balanced_tree this operation can be done in
+ * Due to the nature of a %balance this operation can be done in
* constant time, and only invalidates iterators/references to
* the element being removed. The user is also cautioned that
* this function only erases the element, and that if the element
@@ -535,8 +535,8 @@
* prior to erasing (or end()).
*
* This function will erase the elements in the range @a
- * [first,last) and shorten the %balanced_tree accordingly.
- * Due to the nature of a %balanced_tree this operation can be done in
+ * [first,last) and shorten the %balance accordingly.
+ * Due to the nature of a %balance this operation can be done in
* constant time, and only invalidates iterators/references to
* the elements being removed. The user is also cautioned that
* this function only erases the elements, and that if the
@@ -557,7 +557,7 @@
}
/**
- * Returns true if the %balanced_tree is empty. (Thus begin() would
+ * Returns true if the %balance is empty. (Thus begin() would
* equal end().)
*/
bool empty() const
@@ -576,4 +576,4 @@
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_BALANCED_TREE_HPP
+#endif // BOOST_TREE_balance_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
+++ (empty file)
@@ -1,579 +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)
-
-/**
- * @file balanced_tree.hpp
- * Balanced tree implementation
- */
-
-
-#ifndef BOOST_TREE_BALANCED_TREE_HPP
-#define BOOST_TREE_BALANCED_TREE_HPP
-
-#include <boost/tree/cursor.hpp>
-#include <boost/tree/iterator.hpp>
-
-#include <boost/tree/detail/balancers/unbalanced.hpp>
-#include <boost/tree/detail/augmentors/unaugmented.hpp>
-
-#include <boost/tree/inorder_algorithms.hpp>
-#include <boost/tree/detail/augmented_iterator.hpp>
-
-#include <boost/bind.hpp>
-#include <boost/multi_index/member.hpp>
-
-#include <iterator>
-#include <memory>
-
-namespace boost {
-namespace tree {
-
-using detail::ascending_node;
-using detail::ascending_nary_cursor;
-
-using detail::augmented_iterator;
-
-using boost::multi_index::member;
-
-struct empty_class { };
-
-// TODO: Remove Meta2. This stuff must be done via some MPL magic.
-
-template <class Val, class Meta, class Meta2 = empty_class>
-struct augmented_type {
- typedef Val value_type;
- typedef Meta metadata_type;
-// struct metadata_type : public Meta, public Meta2 {
-// metadata_type() : Meta(), Meta2() {}
-// };
-
- value_type data;
- metadata_type meta;
-
- augmented_type(value_type const& d = value_type()
- , metadata_type const& m = metadata_type())
- : data(d), meta(m) {}
-
- augmented_type(augmented_type const& x)
- : data(x.data), meta(x.meta) {}
-
- metadata_type& metadata()
- {
- return meta;
- }
-
- metadata_type const& metadata() const
- {
- return meta;
- }
-
- typedef member<augmented_type,value_type,&augmented_type::data> extract_data;
- typedef member<augmented_type,metadata_type,&augmented_type::meta> extract_meta;
-};
-
-// metadata traits type specialization for augmented_type
-template <class Val, class Meta, class Meta2>
-struct metadata< augmented_type<Val,Meta,Meta2> > {
- typedef typename augmented_type<Val,Meta,Meta2>::metadata_type type;
-};
-
-
-template <class Cursor>
-class is_on_top_cursor
-: public Cursor {
-public:
- is_on_top_cursor()
- : Cursor() {}
-
- is_on_top_cursor(Cursor p)
- : Cursor(p) {}
-
- bool is_root() const
- {
- return this->is_on_top();
- }
-};
-
-//template <class Cursor>
-//class is_on_top_cursor
-//: public cursor_adaptor<is_on_top_cursor<Cursor>
-// , Cursor
-// , boost::use_default
-// , bidirectional_traversal_tag
-// , bidirectional_traversal_tag
-// > {
-//private:
-// struct enabler {};
-//
-//public:
-// //TODO: Tidy up typedefs
-//
-// typedef Cursor base_cursor;
-//
-// typedef is_on_top_cursor<Cursor> cursor;
-// typedef is_on_top_cursor<Cursor const> const_cursor; //FIXME (?)
-//
-// //typedef typename cursor_size<base_cursor>::type size_type;
-//
-// //typedef bidirectional_traversal_tag cursor_category;
-//
-// // Container-specific:
-// typedef cursor iterator; // For (range) concepts' sake, mainly
-//// typedef const_cursor const_iterator;
-//
-// // Common iterator facade stuff
-// is_on_top_cursor()
-// : is_on_top_cursor::cursor_adaptor_() {}
-//
-// explicit is_on_top_cursor(base_cursor p)
-// : is_on_top_cursor::cursor_adaptor_(p) {}
-//
-//private:
-// friend class cursor_core_access;
-// friend class iterator_core_access;
-//
-//public:
-// bool is_root() const
-// {
-// return this->base_reference().is_on_top();
-// }
-//};
-
-template <class Cursor>
-typename is_on_top_cursor<Cursor>::size_type
-index(is_on_top_cursor<Cursor> const& cur)
-{
- return cur.index();
-}
-
-template <class Cursor>
-class balanced_tree_iterator
-: public iterator<inorder, is_on_top_cursor<Cursor> > {
-public:
- balanced_tree_iterator()
- : iterator<inorder, is_on_top_cursor<Cursor> >() {}
-
- explicit balanced_tree_iterator(Cursor p)
- : iterator<inorder, is_on_top_cursor<Cursor> >(p) {}
-
- operator Cursor()
- {
- return Cursor(this->base());
- }
-};
-
-/**
- * @brief A %balanced_tree.
- * This class models the hierarchy concept, the container concept and the
- * sequence concept. TODO: complete this...
- *
-*/
-template <class Hierarchy, class Balance>
-class balanced_tree {
- public:
- typedef typename Hierarchy::value_type value_type;
- typedef Balance balancer_type;
-
- typedef typename Balance::metadata_type metadata_type;
-
- typedef augmented_type< value_type, metadata_type,
- typename metadata<value_type>::type > data_type;
- typedef typename Hierarchy::template rebind<data_type>::other hierarchy_type;
-
- protected:
- hierarchy_type h;
-
- private:
- typedef balanced_tree<Hierarchy, Balance> self_type;
-
- typedef typename hierarchy_type::cursor cursor;
- typedef typename hierarchy_type::const_cursor const_cursor;
-
- public:
- typedef augmented_iterator<balanced_tree_iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
- typedef augmented_iterator<balanced_tree_iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
-
- typedef std::reverse_iterator<iterator> reverse_iterator;
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-
- typedef typename hierarchy_type::allocator_type allocator_type;
- typedef typename allocator_type::pointer pointer;
- typedef typename allocator_type::reference reference;
- typedef typename allocator_type::size_type size_type;
- typedef typename allocator_type::difference_type difference_type;
-
- explicit balanced_tree (hierarchy_type const& hier = hierarchy_type())
- : h(hier)
- {}
-
- // TODO: 3rd arg...?
- explicit balanced_tree (size_type n, value_type const& value = value_type(),
- hierarchy_type const& hier = hierarchy_type())
- : h(hier)
- {}
-
- template <class InputIterator>
- balanced_tree (InputIterator first, InputIterator last,
- hierarchy_type const& hier = hierarchy_type())
- : h(hier)
- {
- while (first++ != last)
- this->insert(this->end(), *first);
- }
-
- balanced_tree (self_type const& other)
- : h(other.h)
- {}
-
- self_type& operator=(
- self_type const& x);
- template <class InputIterator>
- void assign(InputIterator first, InputIterator last);
- template <class Size, class T>
- void assign(Size n, const T& t = T());
-
- /// Functions returning (inorder) iterators (as required by the Sequence
- /// concept)
-
- /**
- * Returns a read/write ("mutable") iterator to the first (inorder) value.
- */
- iterator begin()
- {
- return iterator(h.inorder_first());
-
- }
-
- /**
- * Returns a read-only const_iterator to the first (inorder) value.
- */
- const_iterator begin() const
- {
- return cbegin();
- }
-
- /**
- * Returns a read-only const_iterator to the first (inorder) value.
- */
- const_iterator cbegin() const
- {
- return const_iterator(h.inorder_cfirst());
- }
-
- /**
- * Returns a read/write ("mutable") inorder iterator to the position one
- * past the last (inorder) value in the %balanced_tree.
- */
- iterator end()
- {
- return iterator(h.root());
- }
-
- /**
- * Returns a read-only inorder const_iterator to the position one past the
- * last (inorder) value in the %balanced_tree.
- */
- const_iterator end() const
- {
- return cend();
- }
-
- /**
- * Returns a read-only inorder const_iterator to the position one past the
- * last (inorder) value in the %balanced_tree.
- */
- const_iterator cend() const
- {
- return const_iterator(h.croot());
- }
-
- /**
- * @brief Finds the first position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using <
- * (less than) for comparisons.
- * @param k The search term
- * @return An iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
- * less than @a k.
- */
- iterator lower_bound(value_type const& k)
- {
- return lower_bound(k, std::less<value_type>());
- }
-
- /**
- * @brief Finds the first position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using <
- * (less than) for comparisons.
- * @param k The search term
- * @return A const_iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
- * less than @a k.
- */
- const_iterator lower_bound(value_type const& k) const
- {
- return lower_bound(k, std::less<value_type>());
- }
-
- /**
- * @brief Finds the first position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using cmp
- * for comparisons.
- * @param k The search term
- * @param cmp The comparison functor
- * @return An iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
- * less than @a k.
- */
- template <class Cmp>
- iterator lower_bound(value_type const& k, Cmp cmp)
- {
- return iterator(boost::tree::lower_bound(h.root(), k,
- bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
- }
-
- /**
- * @brief Finds the first position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using cmp
- * for comparisons.
- * @param k The search term
- * @param cmp The comparison functor
- * @return A const_iterator pointing to the first element not less than
- * @a k, or end() if every element in the @balanced_tree is
- * less than @a k.
- */
- template <class Cmp>
- const_iterator lower_bound(value_type const& k, Cmp cmp) const
- {
- return const_iterator(boost::tree::lower_bound(h.croot(), k,
- bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
- }
-
- /**
- * @brief Finds the last position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using <
- * (less than) for comparisons.
- * @param k The search term
- * @return An iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
- * greater than @a k.
- */
- iterator upper_bound(value_type const& k)
- {
- return upper_bound(k, std::less<value_type>());
- }
-
- /**
- * @brief Finds the last position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using <
- * (less than) for comparisons.
- * @param k The search term
- * @return A const_iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
- * greater than @a k.
- */
- const_iterator upper_bound(value_type const& k) const
- {
- return upper_bound(k, std::less<value_type>());
- }
-
- /**
- * @brief Finds the last position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using cmp
- * for comparisons.
- * @param k The search term
- * @param cmp The comparison functor
- * @return An iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
- * greater than @a k.
- */
- template <class Cmp>
- iterator upper_bound(value_type const& k, Cmp cmp)
- {
- return iterator(boost::tree::upper_bound(h.root(), k,
- bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
- }
-
- /**
- * @brief Finds the last position in the @balanced_tree in which @a k
- * could be inserted without changing the ordering, using cmp
- * for comparisons.
- * @param k The search term
- * @param cmp The comparison functor
- * @return A const_iterator pointing to the first element greater than
- * @a k, or end() if no element in the @balanced_tree is
- * greater than @a k.
- */
- template <class Cmp>
- const_iterator upper_bound(value_type const& k, Cmp cmp) const
- {
- return const_iterator(boost::tree::upper_bound(h.croot(), k,
- bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
- }
-
- /**
- * @brief Add data to the front of the %balanced_tree.
- * @param x Data to be added.
- *
- * This is a typical stack operation. The function creates an
- * element at the front of the %balanced_tree and assigns the given data to
- * it. Due to the nature of a %balanced_tree this operation can be done
- * in constant time, and does not invalidate iterators and references.
- */
- void push_front(value_type const& x)
- {
- insert(begin(), x);
- }
-
- /**
- * @brief Removes first element.
- *
- * This is a typical stack operation. It shrinks the %balance_tree by
- * one. Due to the nature of a %balanced_tree this operation can be done
- * in constant time, and only invalidates iterators/references to
- * the element being removed.
- *
- * Note that no data is returned, and if the first element's data
- * is needed, it should be retrieved before pop_front() is called.
- */
- void pop_front()
- {
- erase(begin());
- }
-
- /**
- * @brief Add data to the end of the %balanced_tree.
- * @param x Data to be added.
- *
- * This is a typical stack operation. The function creates an
- * element at the end of the %balanced_tree and assigns the given data to
- * it. Due to the nature of a %balanced_tree this operation can be done
- * in constant time, and does not invalidate iterators and references.
- */
- void push_back(value_type const& x)
- {
- insert(end(), x);
- }
-
- /**
- * @brief Removes last element.
- *
- * This is a typical stack operation. It shrinks the %balance_tree by
- * one. Due to the nature of a %balanced_tree this operation can be done
- * in constant time, and only invalidates iterators/references to
- * the element being removed.
- *
- * Note that no data is returned, and if the last element's data
- * is needed, it should be retrieved before pop_back() is called.
- */
- void pop_back()
- {
- }
-
- /**
- * @brief Inserts val in front of @a pos.
- * @param pos The %balanced_tree iterator in front of which to insert.
- * @param val The value to insert.
- * @return An inorder iterator that points to the inserted data.
- */
- iterator insert(iterator pos, value_type const& val)
- {
- //TODO: we might need to go down in the hierarchy first
- // That means some redundant work if pos was yielded by upper_bound,
- // so maybe saving two cursors in the iterator would make sense
- // (one for deref, one for insert)
-
- // Then again... that's too much of a fuss. Maybe we should just
- // build a searcher that does all that.
-
- // Do balancers have to work for non-leaf newly inserted elements?
- // If yes, we could just insert at pos.
-
- cursor c = pos.base().base();
- while (!c.empty())
- c = c.end();
-
- c = h.insert(c, data_type(val));
-
- balancer_type::add(h, c);
- return iterator(c.to_begin());
- }
-
- /**
- * @brief Remove element at given position.
- * @param position Iterator pointing to element to be erased.
- * @return An iterator pointing to the next element (or end()).
- *
- * This function will erase the element at the given position and thus
- * shorten the %balanced_tree by one.
- *
- * Due to the nature of a %balanced_tree this operation can be done in
- * constant time, and only invalidates iterators/references to
- * the element being removed. The user is also cautioned that
- * this function only erases the element, and that if the element
- * is itself a pointer, the pointed-to memory is not touched in
- * any way. Managing the pointer is the user's responsibilty.
- */
- iterator erase (iterator position)
- {
- cursor c = position.base().base();
- cursor d = balancer_type::remove(h, c);
-// if (c == d)
- return iterator(h.inorder_erase(c));
-// return iterator(h.inorder_erase(d,c));
- }
-
- /**
- * @brief Remove a range of elements.
- * @param first Iterator pointing to the first element to be erased.
- * @param last Iterator pointing to one past the last element to be
- * erased.
- * @return An iterator pointing to the element pointed to by @a last
- * prior to erasing (or end()).
- *
- * This function will erase the elements in the range @a
- * [first,last) and shorten the %balanced_tree accordingly.
- * Due to the nature of a %balanced_tree this operation can be done in
- * constant time, and only invalidates iterators/references to
- * the elements being removed. The user is also cautioned that
- * this function only erases the elements, and that if the
- * elements themselves are pointers, the pointed-to memory is not
- * touched in any way. Managing the pointers is the user's
- * responsibilty.
- */
- void erase (iterator a, iterator b)
- {
- }
-
- /**
- * @brief Clears all data from the tree.
- */
- void clear()
- {
- h.clear();
- }
-
- /**
- * Returns true if the %balanced_tree is empty. (Thus begin() would
- * equal end().)
- */
- bool empty() const
- {
- return h.empty();
- }
-
- void rotate(iterator& i)
- {
- cursor c = cursor(boost::tree::iterator<inorder, cursor>(i));
- h.rotate(c);
- }
-};
-
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_BALANCED_TREE_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
@@ -151,7 +151,7 @@
template <class MultiwayCursor, class T, class Cmp>
BOOST_CONCEPT_REQUIRES(
((DescendingCursor<MultiwayCursor>))
- /*((LessThanComparable<Cmp>))*/, // Problem with balanced_tree
+ /*((LessThanComparable<Cmp>))*/, // Problem with balance
(MultiwayCursor)) // return type
lower_bound(MultiwayCursor x, T const& val, Cmp cmp)
//]
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
@@ -16,7 +16,7 @@
#include <list>
#include <iterator>
-#include <boost/tree/balanced_tree.hpp>
+#include <boost/tree/balance.hpp>
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
@@ -8,7 +8,7 @@
#define LIBS_TREE_TEST_HELPERS_HPP
//#include <boost/tree/binary_tree.hpp>
-//#include <boost/tree/balanced_tree.hpp>
+//#include <boost/tree/balance.hpp>
//#include <boost/tree/searcher.hpp>
//
//#include <boost/multi_index/identity.hpp>
@@ -41,12 +41,12 @@
//// TODO: Ctor, dtors
//template <class Hier, class Balance>
//struct test_balancer
-// : public balanced_tree<Hier, Balance> {
+// : public balance<Hier, Balance> {
//
-// typedef typename balanced_tree<Hier, Balance>::hierarchy_type hierarchy_type;
+// typedef typename balance<Hier, Balance>::hierarchy_type hierarchy_type;
//
// explicit test_balancer(hierarchy_type const& hier = hierarchy_type())
-// : balanced_tree<Hier, Balance>(hier)
+// : balance<Hier, Balance>(hier)
// {}
//
// hierarchy_type& hierarchy()
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
@@ -22,7 +22,7 @@
{
using namespace boost::tree;
- typedef test_searcher<false, balanced_tree<binary_tree<int>, balancers::unbalanced> > searcher_t;
+ typedef test_searcher<false, balance<binary_tree<int>, balancers::unbalanced> > searcher_t;
searcher_t my_tree;
searcher_t::iterator c, c1, c2, c3, c4, c5;
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp 2009-01-14 16:59:50 EST (Wed, 14 Jan 2009)
@@ -4,7 +4,7 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#include <boost/tree/balanced_tree.hpp>
+#include <boost/tree/balance.hpp>
#include <boost/tree/detail/balancers/unbalanced.hpp>
#include <boost/tree/binary_tree.hpp>
@@ -19,7 +19,7 @@
using namespace boost::tree;
typedef binary_tree<int> tree_t;
- typedef balanced_tree<tree_t, balancers::unbalanced> balancer_t;
+ typedef balance<tree_t, balancers::unbalanced> balancer_t;
balancer_t my_tree;
balancer_t::iterator c, c1, c2, c3, c4, c5;