[Boost-commit] svn:boost r50600 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test

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;