[Boost-commit] svn:boost r46236 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/augmentors boost/tree/balancers boost/tree/comparators boost/tree/detail/augmentors boost/tree/detail/balancers boost/tree/detail/comparators libs/tree/test

From: ockham_at_[hidden]
Date: 2008-06-08 09:07:21

Author: bernhard.reiter
Date: 2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
New Revision: 46236
URL: http://svn.boost.org/trac/boost/changeset/46236

Log:
Directory and file cleanup, part 7. We're getting there.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/
      - copied from r43517, /sandbox/SOC/2006/tree/trunk/boost/tree/augmentors/
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/interval.hpp
      - copied unchanged from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/augmentors/interval.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/rank.hpp
      - copied unchanged from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/augmentors/rank.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/unaugmented.hpp
      - copied unchanged from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/augmentors/unaugmented.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/
      - copied from r43517, /sandbox/SOC/2006/tree/trunk/boost/tree/balancers/
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp
      - copied unchanged from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/balancers/red_black.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp
      - copied unchanged from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/balancers/treap.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp
      - copied unchanged from r46232, /sandbox/SOC/2006/tree/trunk/boost/tree/balancers/unbalanced.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/comparators/
      - copied from r43517, /sandbox/SOC/2006/tree/trunk/boost/tree/comparators/
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/comparators/string.hpp
      - copied unchanged from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/comparators/string.hpp
Removed:
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_iterator.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/augmentors/
   sandbox/SOC/2006/tree/trunk/boost/tree/balancers/
   sandbox/SOC/2006/tree/trunk/boost/tree/comparators/
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/search.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp                   |     4 ++--                                    
   sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp |     2 +-                                      
   2 files changed, 3 insertions(+), 3 deletions(-)

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,63 +0,0 @@
-//  Copyright (c) 2006-2008, 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 ascending.hpp
- * Ascending traversal algorithms for cursors
- */
-//TODO:
-// Concept checks: MultiwayTree, parent?
-// Optimise for trees such as binary_tree with their own ascending begin() members!
-
-#ifndef BOOST_TREE_ASCENDING_HPP
-#define BOOST_TREE_ASCENDING_HPP
-
-#include <boost/tree/cursor.hpp>
-
-#include <boost/iterator/iterator_categories.hpp>
-
-
-namespace boost {
-namespace tree {
-
-namespace ascending {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-/**
- * @brief	Ascending successor
- * @param c	MultiwayCursor to be set to its ascending successor
- * @ingroup	traversal
- */
-template <class MultiwayCursor>
-inline void forward(MultiwayCursor& c)
-{
-	c.to_parent();
-	return;
-}
-
-/**
- * @brief	Ascending successor
- * @param c	A cursor
- * @return	Ascending successor of @a c
- * @ingroup	traversal
- */
-template <class MultiwayCursor>
-inline MultiwayCursor next(MultiwayCursor c)
-{
-	forward(c);
-	return c;
-}
-
-/*\@}*/
-
-} // namespace ascending
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_ASCENDING_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_iterator.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,79 +0,0 @@
-//  Copyright (c) 2006-2008, 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 ascending_iterator.hpp
- * Ascending iterator wrapper around cursor.
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_ASCENDING_ITERATOR_HPP
-#define BOOST_TREE_ASCENDING_ITERATOR_HPP
-
-#include <boost/tree/ascending.hpp>
-#include <boost/tree/cursor.hpp>
-
-#include <boost/iterator/iterator_adaptor.hpp>
-#include <boost/type_traits/is_convertible.hpp>
-#include <boost/utility/enable_if.hpp>
-
-namespace boost {
-namespace tree {
-	
-namespace ascending {
-
-template <class Cursor, class Tag = typename cursor_category<Cursor>::type>
-class iterator;
-
-template <class Cursor>
-class iterator<Cursor, bidirectional_traversal_tag>
- : public boost::iterator_adaptor<iterator<Cursor, bidirectional_traversal_tag>
-      , Cursor
-      , boost::use_default
-      , forward_traversal_tag
-    > {
- private:
-    struct enabler {};
-
- public:
-    iterator()
-      : iterator::iterator_adaptor_() {}
-
-    explicit iterator(Cursor p)
-      : iterator::iterator_adaptor_(p) {}
-
-    template <class OtherCursor>
-    iterator(
-        iterator<OtherCursor> const& other
-      , typename boost::enable_if<
-            boost::is_convertible<OtherCursor,Cursor >
-          , enabler
-        >::type = enabler()
-    )
-      : iterator::iterator_adaptor_(other.base()) {}
-
-	operator Cursor()
-	{
-		return this->base();
-	}
- private:
-    friend class boost::iterator_core_access;
-    
-    void increment()
-    {
-		forward(this->base_reference());
-    }
-    
-};
-
-
-} // namespace ascending
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_ASCENDING_ITERATOR_HPP

Modified: 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/balanced_tree.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
@@ -16,8 +16,8 @@
 #include <boost/tree/cursor.hpp>
 #include <boost/tree/iterator.hpp>
 
-#include <boost/tree/balancers/unbalanced.hpp>
-#include <boost/tree/augmentors/unaugmented.hpp>
+#include <boost/tree/detail/balancers/unbalanced.hpp>
+#include <boost/tree/detail/augmentors/unaugmented.hpp>
 
 #include <boost/tree/detail/algorithm/cursor/inorder.hpp>
 #include <boost/tree/detail/iterator/augmented.hpp>

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,125 +0,0 @@
-//  Copyright (c) 2006-2008, 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 inorder.hpp
- * Inorder traversal algorithms for cursors
- */
-//TODO:
-// Concept checks: MultiwayTree, parent?
-// Optimise for trees such as binary_tree with their own inorder begin() members!
-
-#ifndef BOOST_TREE_INORDER_HPP
-#define BOOST_TREE_INORDER_HPP
-
-#include <boost/tree/cursor.hpp>
-
-#include <boost/iterator/iterator_categories.hpp>
-
-
-namespace boost {
-namespace tree {
-
-namespace inorder {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-/**
- * @brief	Inorder successor
- * @param c	MultiwayCursor to be set to its inorder successor
- * @ingroup	traversal
- */
-template <class MultiwayCursor>
-inline void forward(MultiwayCursor& c)
-{
-	if (!(++c).empty()) {
-		while (!c.to_begin().empty());
-		return;
-	}
-	
-	while (c.parity()) // Doesn't work with subtrees whose root's parity != 0
-		c.to_parent();
-	return;
-}
-
-/**
- * @brief	Inorder successor
- * @param c	A cursor
- * @return	Inorder successor of @a c
- * @ingroup	traversal
- */
-template <class MultiwayCursor>
-inline MultiwayCursor next(MultiwayCursor c)
-{
-	forward(c);
-	return c;
-}
-
-/**
- * @brief	Inorder predecessor
- * @param c	MultiwayCursor to be set to its inorder predecessor
- */
-template <class MultiwayCursor>
-inline void back(MultiwayCursor& c)
-{
-    if (!c.empty()) {
-		while (!c.to_end().empty());
-		--c;
-		return;
-	}
-	while (!c.parity())
-		c.to_parent();
-	--c;
-	return;
-}
-
-/**
- * @brief	Inorder predecessor
- * @param c	MultiwayCursor
- * @return	Inorder predecessor of @a c
- */
-template <class MultiwayCursor>
-inline MultiwayCursor prior(MultiwayCursor c)
-{
-	back(c);
-	return c;
-}
-
-/**
- * @brief	First element of a Multiway subtree in inorder traversal
- * @param c	A MultiwayCursor
- * @return	Cursor to the first element of @a c in inorder traversal
- */
-template <class MultiwayCursor>
-MultiwayCursor first(MultiwayCursor c)
-{
-	while (!c.empty())
-		c.to_begin();
-	return c;
-}
-
-/**
- * @brief	One position past the last element of a Multiway subtree in 
- * 			inorder traversal
- * @param c	A MultiwayCursor
- * @return	Cursor one position past the last element of @a c in inorder
- * 			traversal
- */
-template <class MultiwayCursor>
-MultiwayCursor last(MultiwayCursor c)
-{
-	return c;
-}
-
-/*\@}*/
-
-} // namespace inorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_INORDER_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,123 +0,0 @@
-//  Copyright (c) 2006-2008, 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 inorder_iterator.hpp
- * Inorder iterator wrapper around cursor.
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_INORDER_ITERATOR_HPP
-#define BOOST_TREE_INORDER_ITERATOR_HPP
-
-
-#include <boost/tree/inorder.hpp>
-#include <boost/tree/cursor.hpp>
-
-#include <boost/iterator/iterator_adaptor.hpp>
-#include <boost/type_traits/is_convertible.hpp>
-#include <boost/utility/enable_if.hpp>
-
-#include <stack>
-
-
-using std::stack;
-
-namespace boost {
-namespace tree {
-	
-namespace inorder {
-
-template <class MultiwayCursor, 
-		  class Tag = typename cursor_vertical_traversal<MultiwayCursor>::type>
-class iterator;
-
-template <class MultiwayCursor>
-class iterator<MultiwayCursor, forward_traversal_tag>
- : public boost::iterator_facade<iterator<MultiwayCursor, forward_traversal_tag>
-      , typename MultiwayCursor::value_type
-      , bidirectional_traversal_tag
-    > {
-// private:
-//    struct enabler {};
-
- public:
-    iterator() {}
-//      : iterator::iterator_adaptor_() {}
-
-    explicit iterator(stack<MultiwayCursor> s) 
-    		: m_s(s) {}
-//      : iterator::iterator_adaptor_(p) {}
-
-//    template <class OtherMultiwayCursor>
-//    iterator(
-//        iterator<OtherMultiwayCursor> const& other
-//      , typename boost::enable_if<
-//            boost::is_convertible<OtherMultiwayCursor,MultiwayCursor >
-//          , enabler
-//        >::type = enabler()
-//    )
-//      : iterator::iterator_adaptor_(other.base()) {}
-
-	operator MultiwayCursor()
-	{
-		return m_s.top();
-	}
- private:
-    friend class boost::iterator_core_access;
-
- 	stack<MultiwayCursor> m_s;
-    
-    typename MultiwayCursor::value_type& dereference() const
-    {
-    		return *m_s.top();
-    	}
-    
-    bool equal(iterator<MultiwayCursor, forward_traversal_tag> const& other) const
-    {
-    		return (this->m_s == other.m_s);
-    }
-    
-    void increment()
-    {
-		if (!(++m_s.top()).empty()) {
-			while (!m_s.top().begin().empty())
-				m_s.push(m_s.top().begin());
-			m_s.push(m_s.top().begin());
-			return;
-		}
-		
-		while (m_s.top().parity() && !m_s.empty())
-			m_s.pop();
-		return;
-    }
-    
-    void decrement()
-    {
-	    if (!m_s.top().empty()) {	    		
-			while (!m_s.top().end().empty())
-				m_s.push(m_s.top().end());
-			m_s.push(m_s.top().begin());
-			return;
-		}
-		
-		while (!m_s.top().parity())
-			m_s.pop();
-		--m_s.top();
-		return;
-    }
-};
-
-#include <boost/tree/detail/iterator/bidirectional.hpp>
-
-
-} // namespace inorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_INORDER_ITERATOR_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,152 +0,0 @@
-//  Copyright (c) 2006-2008, 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 postorder.hpp
- * Postorder traversal algorithms for cursors
- */
-// TODO: Concept checks: Non-MultiwayTree or forest, parent?
-
-#ifndef BOOST_TREE_POSTORDER_HPP
-#define BOOST_TREE_POSTORDER_HPP
-
-#include <boost/tree/cursor.hpp>
-
-#include <boost/iterator/iterator_categories.hpp>
-
-namespace boost {
-namespace tree {
-
-namespace postorder {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-/**
- * @brief	Postorder successor
- * @param c	Cursor to be set to its postorder successor
- */
-template <class Cursor>
-inline void forward(Cursor& c)
-{
-	c.to_parent();
-
-	if (c.parity()) { // Right child? Return parent.
-		--c;
-		return;
-	}
-	
-	if (c.parent().begin() != c) // Root?
-		return;
-	
-	// Left child.
-	++c;
-	while (!c.empty()) {
-		c.to_begin();
-		if (c.empty())
-			++c;
-	}
-	if (c.parity())
-		--c;
-	return;
-}
-
-/**
- * @brief	Postorder successor
- * @param c	A cursor
- * @return	Postorder successor of @a c
- */
-template <class Cursor>
-inline Cursor next(Cursor c)
-{
-	forward(c);
-	return c;
-}
-
-/**
- * @brief	Postorder predecessor
- * @param c	Cursor to be set to its postorder predecessor
- */
-template <class Cursor>
-inline void back(Cursor& c)
-{
-	if (!c.parity() && (c.parent().begin() != c)) { // Root?
-		c.to_begin();
-		return;
-	}
-	
-	if (!(++c).empty()) { // Right
-		c.to_begin();
-		return;
-	}
-	if (!(--c).empty()) { // Left
-		c.to_begin();
-		return;
-	}
-	
-	// Move up in the hierarchy until we find a descendant that has a right
-	// child (which is what we'll return) or we land at root.
-	while (true) { // revisit
-		c.to_parent();
-		if (c.parity())
-			if (!(--c).empty()) {
-				c.to_begin();
-				return;
-			}
-	}
-	return;
-}
-
-/**
- * @brief	Postorder predecessor
- * @param c	A cursor
- * @return	Postorder predecessor of @a c
- */
-template <class Cursor>
-inline Cursor prior(Cursor c)
-{
-	back(c);
-	return c;
-}
-
-/**
- * @brief	First element of a subtree in postorder traversal
- * @param c	A cursor
- * @return	Cursor to the first element of @a c in postorder traversal
- */
-template <class Cursor>
-Cursor first(Cursor c)
-{
-	while (true)
-		if (!c.empty())
-			c.to_begin();
-		else if (!(++c).empty())
-			c.to_begin();
-		else
-			return --c;
-}
-
-/**
- * @brief	One position past the last element of a subtree in postorder 
- * 			traversal
- * @param c	A cursor
- * @return	Cursor one position past the last element of @a c in 
- * 			postorder traversal
- */
-template <class Cursor>
-Cursor last(Cursor c)
-{
-	return c;
-}
-
-/*\@}*/
-
-} // namespace postorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_POSTORDER_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,142 +0,0 @@
-//  Copyright (c) 2006-2008, 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 postorder_iterator.hpp
- * Postorder iterator wrapper around cursor.
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_POSTORDER_ITERATOR_HPP
-#define BOOST_TREE_POSTORDER_ITERATOR_HPP
-
-
-#include <boost/tree/postorder.hpp>
-
-#include <boost/iterator/iterator_adaptor.hpp>
-#include <boost/type_traits/is_convertible.hpp>
-#include <boost/utility/enable_if.hpp>
-
-
-namespace boost {
-namespace tree {
-	
-namespace postorder {
-
-template <class Cursor, 
-		  class Tag = typename cursor_vertical_traversal<Cursor>::type>
-class iterator;
-
-template <class Cursor>
-class iterator<Cursor, forward_traversal_tag>
- : public boost::iterator_facade<iterator<Cursor, forward_traversal_tag>
-      , typename Cursor::value_type
-      , bidirectional_traversal_tag
-    > {
-// private:
-//    struct enabler {};
-
- public:
-    iterator() {}
-//      : iterator::iterator_adaptor_() {}
-
-    explicit iterator(stack<Cursor> s) 
-    		: m_s(s) {}
-//      : iterator::iterator_adaptor_(p) {}
-
-//    template <class OtherCursor>
-//    iterator(
-//        iterator<OtherCursor> const& other
-//      , typename boost::enable_if<
-//            boost::is_convertible<OtherCursor,Cursor >
-//          , enabler
-//        >::type = enabler()
-//    )
-//      : iterator::iterator_adaptor_(other.base()) {}
-
-	operator Cursor()
-	{
-		return m_s.top();
-	}
- private:
-    friend class boost::iterator_core_access;
-
- 	stack<Cursor> m_s;
-    
-    typename Cursor::value_type& dereference() const
-    {
-    		return *m_s.top();
-    	}
-    
-    bool equal(iterator<Cursor, forward_traversal_tag> const& other) const
-    {
-    		return (this->m_s == other.m_s);
-    }
-    
-    void increment()
-    {
-		m_s.pop();
-		
-		if (m_s.top().parity()) { // Right child? Return parent.
-			--m_s.top();
-			return;
-		}
-		
-		if (m_s.size() == 1) // Root?
-			return;
-			
-		// Left child.
-		++m_s.top();
-		while (!m_s.top().empty()) {
-			m_s.push(m_s.top().begin());
-			if (m_s.top().empty())
-				++m_s.top();
-		}
-		if (m_s.top().parity())
-			--m_s.top();
-		return;
-    }
-    
-    void decrement()
-    {
-		if (m_s.size() == 1) { // Root?
-			m_s.push(m_s.top().begin());
-			return;
-		}
-		
-		if (!(++m_s.top()).empty()) { // Right
-			m_s.push(m_s.top().begin());
-			return;
-		}
-		if (!(--m_s.top()).empty()) { // Left
-			m_s.push(m_s.top().begin());
-			return;
-		}
-		
-		// Move up in the hierarchy until we find a descendant that has a right
-		// child (which is what we'll return) or we land at root.
-		while (true) {
-			m_s.pop();
-			if (m_s.top().parity())
-				if (!(--m_s.top()).empty()) {
-					m_s.push(m_s.top().begin());
-					return;
-				}
-		}
-		return;
-    }
-};
-
-#include <boost/tree/detail/iterator/bidirectional.hpp>
-
-
-} // namespace postorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_POSTORDER_ITERATOR_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,155 +0,0 @@
-//  Copyright (c) 2006-2008, 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 preorder.hpp
- * Preorder traversal algorithms for cursors
- */
-// TODO: Concept checks: Non-MultiwayTree or forest, parent?
-
-#ifndef BOOST_TREE_PREORDER_HPP
-#define BOOST_TREE_PREORDER_HPP
-
-#include <boost/tree/cursor.hpp>
-
-#include <boost/iterator/iterator_categories.hpp>
-
-namespace boost {
-namespace tree {
-
-namespace preorder {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-/**
- * @brief	Preorder successor
- * @param c	Cursor to be set to its preorder successor
- */
-template <class Cursor>
-inline void forward(Cursor& c)
-{
-	// If we have a left child, go there.
-	if (!c.empty()) {
-		c.to_begin();
-		return;
-	}
-	
-	// No left child. So if we have a right child, go there.
-	if (!(++c).empty()) {
-		c.to_begin();
-		return;
-	}
-	
-	// (Here's where we'd need to check if this is the end().)
-	
-	// No children at all.
-	// As we've already visited all the ancestors, we'll move upwards until
-	// we find an ancestor that has a right child.
-	while (true) { // Doesn't work with subtrees!
-		if (!c.parity() && (c != c.parent().begin())) // Root
-			return;
-		
-		c.to_parent();
-		if (!c.parity()) {
-			if (c != c.parent().begin()) // Root?
-				return;
-			if (!(++c).empty()) {
-				c.to_begin();
-				return;
-			}
-		}
-	}
-	return;
-}
-
-/**
- * @brief	Preorder successor
- * @param c	A cursor
- * @return	Preorder successor of @a c
- */
-template <class Cursor>
-inline Cursor next(Cursor c)
-{
-	forward(c);
-	return c;
-}
-
-/**
- * @brief	Preorder predecessor
- * @param c	Cursor to be set to its preorder predecessor
- */
-template <class Cursor>
-inline void back(Cursor& c)
-{
-	if (!(!c.parity() && (c != c.parent().begin()))) { // Not root
-		c.to_parent();
-		
-		// If this is a left child, just move to its parent.
-		if (!c.parity()) {
-			c.to_parent();
-			c.to_begin();
-			return;
-		}
-		
-		// So this is a right child.
-		--c;
-	}
-	
-	// Same for root (=end) and right children:
-	if (!c.empty())
-		while (!c.empty())
-			if (!c.end().empty())
-				c.to_end();
-			else
-				c.to_begin();
-	return;
-}
-
-/**
- * @brief	Preorder predecessor
- * @param c	A cursor
- * @return	Preorder predecessor of @a c
- */
-template <class Cursor>
-inline Cursor prior(Cursor c)
-{
-	back(c);
-	return c;
-}
-
-/**
- * @brief	First element of a subtree in preorder traversal
- * @param c	A cursor
- * @return	Cursor to the first element of @a c in preorder traversal
- */
-template <class Cursor>
-Cursor first(Cursor c)
-{
-	return c.begin();
-}
-
-/**
- * @brief	One position past the last element of a subtree in preorder 
- * 			traversal
- * @param c	A cursor
- * @return	Cursor one position past the last element of @a c in preorder
- * 			traversal
- */
-template <class Cursor>
-Cursor last(Cursor c)
-{
-	return c;
-}
-
-/*\@}*/
-
-} // namespace preorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_PREORDER_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,151 +0,0 @@
-//  Copyright (c) 2006-2008, 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 preorder_iterator.hpp
- * Preorder iterator wrapper around cursor.
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_PREORDER_ITERATOR_HPP
-#define BOOST_TREE_PREORDER_ITERATOR_HPP
-
-
-#include <boost/tree/preorder.hpp>
-
-#include <boost/iterator/iterator_adaptor.hpp>
-#include <boost/type_traits/is_convertible.hpp>
-#include <boost/utility/enable_if.hpp>
-
-
-namespace boost {
-namespace tree {
-	
-namespace preorder {
-
-template <class Cursor, 
-		  class Tag = typename cursor_vertical_traversal<Cursor>::type>
-class iterator;
-
-template <class Cursor>
-class iterator<Cursor, forward_traversal_tag>
- : public boost::iterator_facade<iterator<Cursor, forward_traversal_tag>
-      , typename Cursor::value_type
-      , bidirectional_traversal_tag
-    > {
-// private:
-//    struct enabler {};
-
- public:
-    iterator() {}
-//      : iterator::iterator_adaptor_() {}
-
-    explicit iterator(stack<Cursor> s) 
-    		: m_s(s) {}
-//      : iterator::iterator_adaptor_(p) {}
-
-//    template <class OtherCursor>
-//    iterator(
-//        iterator<OtherCursor> const& other
-//      , typename boost::enable_if<
-//            boost::is_convertible<OtherCursor,Cursor >
-//          , enabler
-//        >::type = enabler()
-//    )
-//      : iterator::iterator_adaptor_(other.base()) {}
-
-	operator Cursor()
-	{
-		return m_s.top();
-	}
- private:
-    friend class boost::iterator_core_access;
-
- 	stack<Cursor> m_s;
-    
-    typename Cursor::value_type& dereference() const
-    {
-    		return *m_s.top();
-    	}
-    
-    bool equal(iterator<Cursor, forward_traversal_tag> const& other) const
-    {
-    		return (this->m_s == other.m_s);
-    }
-    
-    void increment()
-    {
-		// If we have a left child, go there.
-		if (!m_s.top().empty()) {
-			m_s.push(m_s.top().begin());
-			return;
-		}
-		
-		// No left child. So if we have a right child, go there.
-		if (!(++m_s.top()).empty()) {
-			m_s.push(m_s.top().begin());
-			return;
-		}
-		
-		// (Here's where we'd need to check if this is the end().)
-		
-		// No children at all.
-		// As we've already visited all the ancestors, we'll move upwards until
-		// we find an ancestor that has a right child.
-		while (true) { // Doesn't work with subtrees!
-			if (m_s.size() == 1) // Root
-				return;
-
-			m_s.pop();
-			if (!m_s.top().parity()) {
-				if (m_s.size() == 1) // Root?
-					return;
-				if (!(++m_s.top()).empty()) {
-					m_s.push(m_s.top().begin());
-					return;
-				}
-			}
-		}
-		return;
-}
-    
-    void decrement()
-    {
-		if (m_s.size() != 1) { // Not root
-			m_s.pop();
-			
-			// If this is a left child, just move to its parent.
-			if (!m_s.top().parity()) {
-				m_s.pop();
-				m_s.push(m_s.top().begin());
-				return;
-			}
-			
-			// So this is a right child.
-			--m_s.top();
-		}
-		
-		// Same for root (=end) and right children:
-		if (!m_s.top().empty())
-			while (!m_s.top().empty())
-				if (!m_s.top().end().empty())
-					m_s.push(m_s.top().end());
-				else
-					m_s.push(m_s.top().begin());
-		return;
-    }
-};
-
-#include <boost/tree/detail/iterator/bidirectional.hpp>
-
-
-} // namespace preorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_PREORDER_ITERATOR_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/search.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/search.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,84 +0,0 @@
-//  Copyright (c) 2006-2008, 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 search.hpp
- * Generalized binary (tree) search algorithms
- */
- 
-// TODO: 
-// * Concept checks all over.
-// * add versions without cmp argument (just using <)
-
-// concept checks etc. ATM binary only, generalize for actual Multiway.
-// 2/3 argument versions (using tree instead of root)
-//(and specialize again using "trivial lower bound" instead of std::lower_bound)
-//internally - or provide one lower bound for all. (for example a range version)
-// (See "exercises"!)
-
-#ifndef BOOST_TREE_SEARCH_HPP
-#define BOOST_TREE_SEARCH_HPP
-
-#include <algorithm>
-
-namespace boost {
-namespace tree {
-
-namespace inorder {
-
-/**
- * @brief		Finds the first position in a multiway subtree in which @a val 
- * 				could be inserted without changing the ordering, using < (less
- * 				than) for comparisons.
- * @param x		The subtree's root
- * @param val	The search term
- * @return		A multiway cursor pointing to the first element not less than 
- *				@a val, or @x if every element in the subtree is less than 
- * 				@a val.
- */
-template <class MultiwayCursor, class T>
-MultiwayCursor lower_bound(MultiwayCursor x, T const& val)
-{
-	MultiwayCursor y = x;
-	while (!x.empty()) {
-		x = std::lower_bound(x.begin(), x.end(), val);
-		if (x.parity() == 0)
-			y = x;
-	}
-	return y;
-}
-
-/**
- * @brief		Finds the first position in a multiway subtree in which @a val 
- * 				could be inserted without changing the ordering, using @a cmp 
- * 				for comparisons.
- * @param x		The subtree's root
- * @param val	The search term
- * @param cmp	The comparison functor
- * @return		A multiway cursor pointing to the first element not less than 
- *				@a val, or @x if every element in the subtree is less than 
- * 				@a val.
- */
-template <class MultiwayCursor, class T, class Cmp>
-MultiwayCursor lower_bound(MultiwayCursor x, T const& val, Cmp cmp)
-{
-	MultiwayCursor y = x;
-	while (!x.empty()) {
-		x = std::lower_bound(x.begin(), x.end(), val, cmp);
-		if (x.parity() == 0)
-			y = x;
-	}
-	return y;
-}
-
-} // namespace inorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_SEARCH_HPP
-
-

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,23 +0,0 @@
-//  Copyright (c) 2006-2008, 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 traversal.hpp
- * Various traversal algorithms for cursors
- */
-
-#ifndef BOOST_TREE_TRAVERSAL_HPP
-#define BOOST_TREE_TRAVERSAL_HPP
-
-#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
-#include <boost/tree/detail/algorithm/cursor/preorder.hpp>
-#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
-
-#include <boost/tree/detail/algorithm/iterator/inorder.hpp>
-#include <boost/tree/detail/algorithm/iterator/preorder.hpp>
-#include <boost/tree/detail/algorithm/iterator/postorder.hpp>
-
-#endif // BOOST_TREE_TRAVERSAL_HPP

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	2008-06-08 09:07:20 EDT (Sun, 08 Jun 2008)
@@ -7,7 +7,7 @@
 #include <boost/test/minimal.hpp>
 
 #include <boost/tree/balanced_tree.hpp>
-#include <boost/tree/balancers/unbalanced.hpp>
+#include <boost/tree/detail/balancers/unbalanced.hpp>
 #include <boost/tree/binary_tree.hpp>
 
 //#include <boost/tree/searcher.hpp>