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>