Subject: [Boost-commit] svn:boost r50442 - in sandbox/SOC/2006/tree/trunk/boost/tree: . detail detail/balancers detail/cursor
From: ockham_at_[hidden]
Date: 2009-01-02 14:29:42
Author: bernhard.reiter
Date: 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
New Revision: 50442
URL: http://svn.boost.org/trac/boost/changeset/50442
Log:
Continue detail directory re-organization.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/multiway_cursor.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/node_traits.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 8 ++++----
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 8 ++++----
9 files changed, 15 insertions(+), 15 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -16,8 +16,8 @@
#include <boost/tree/algorithm.hpp>
#include <boost/tree/insert_cursor.hpp>
-#include <boost/tree/detail/node/traits.hpp>
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/node_traits.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <memory>
@@ -47,9 +47,9 @@
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
- typedef typename node_traits<node_type>::node_base_type node_base_type;
+ typedef typename detail::node_traits<node_type>::node_base_type node_base_type;
typedef node_base_type* node_base_pointer;
- typedef typename node_traits<node_type>::node_pointer node_pointer;
+ typedef typename detail::node_traits<node_type>::node_pointer node_pointer;
public:
typedef ascending_nary_cursor<node_type> cursor;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -11,7 +11,7 @@
//TODO: lots.
//templatize with bool add_data?
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
namespace boost {
namespace tree {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -13,7 +13,7 @@
#ifndef BOOST_TREE_BALANCERS_TREAP_HPP
#define BOOST_TREE_BALANCERS_TREAP_HPP
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <limits.h>
#include <stdlib.h>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -7,7 +7,7 @@
#ifndef BOOST_TREE_BALANCERS_UNBALANCED_HPP
#define BOOST_TREE_BALANCERS_UNBALANCED_HPP
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <boost/tree/inorder_algorithms.hpp>
namespace boost {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -9,7 +9,7 @@
#ifndef BOOST_TREE_DETAIL_CURSOR_MULTIWAY_HPP
#define BOOST_TREE_DETAIL_CURSOR_MULTIWAY_HPP
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <boost/tree/cursor.hpp>
#include <boost/tree/cursor_adaptor.hpp>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -14,7 +14,7 @@
#include <boost/tree/cursor.hpp>
#include <boost/tree/cursor_adaptor.hpp>
-#include <boost/tree/detail/node/nary.hpp>
+#include <boost/tree/detail/nary_node.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,132 @@
+// 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 forest_cursor.hpp
+ * Forest cursor template
+ */
+
+#ifndef BOOST_TREE_DETAIL_FOREST_CURSOR_HPP
+#define BOOST_TREE_DETAIL_FOREST_CURSOR_HPP
+
+#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_adaptor.hpp>
+
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/utility/enable_if.hpp>
+
+#include <iterator>
+#include <utility>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+using boost::tree::cursor_core_access;
+using boost::iterator_core_access;
+
+template <class Cursor>
+class forest_cursor
+: public cursor_adaptor<forest_cursor<Cursor>
+ , Cursor
+ , boost::use_default
+ , bidirectional_traversal_tag
+ , ascending_vertical_traversal_tag
+ > {
+
+private:
+ struct enabler {};
+
+public:
+ //TODO: Tidy up typedefs
+
+ typedef Cursor base_cursor;
+
+ typedef forest_cursor<Cursor> cursor;
+ typedef forest_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
+ forest_cursor()
+ : forest_cursor::cursor_adaptor_() {}
+
+ explicit forest_cursor(base_cursor p)
+ : forest_cursor::cursor_adaptor_(p) {}
+
+ template <class OtherCursor>
+ forest_cursor(
+ forest_cursor<OtherCursor> const& other
+ , typename boost::enable_if<
+ boost::is_convertible<OtherCursor*,
+ typename Cursor::base_pointer> // is that correct?
+ , enabler
+ >::type = enabler()
+ )
+ : forest_cursor::cursor_adaptor_(other.base()) {}
+
+ operator base_cursor()
+ {
+ return forest_cursor::cursor_adaptor_::base();
+ }
+
+ Cursor const& base() const
+ {
+ return forest_cursor::cursor_adaptor_::base();
+ }
+private:
+
+ friend class cursor_core_access;
+ friend class iterator_core_access;
+
+ bool empty_() const
+ {
+ return this->base().begin().empty() && this->base().end().empty();
+ }
+
+ typename forest_cursor::cursor_adaptor_::reference dereference() const
+ {
+ return *this->base_reference().begin();
+ }
+
+ void increment()
+ {
+ this->base_reference().to_end();
+ }
+
+ void decrement()
+ {
+ this->base_reference().to_parent();
+ }
+
+ // Range stuff.
+
+ // left() remains unchanged, so no need to re-implement it.
+
+ void right()
+ {
+ to_forest_end(this->base_reference());
+ }
+
+ // Cursor stuff.
+
+ void up()
+ {
+ to_forest_parent(this->base_reference());
+ }
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_FOREST_CURSOR_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/multiway_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/multiway_cursor.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,181 @@
+// 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 multiway_cursor.hpp
+ * Multiway cursor template
+ */
+
+#ifndef BOOST_TREE_DETAIL_MULTIWAY_CURSOR_HPP
+#define BOOST_TREE_DETAIL_MULTIWAY_CURSOR_HPP
+
+#include <boost/tree/detail/nary_cursor.hpp>
+
+#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_adaptor.hpp>
+
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/utility/enable_if.hpp>
+
+#include <iterator>
+#include <utility>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+template <class Cursor>
+class multiway_tree_cursor;
+
+template<class Cursor>
+class const_multiway_tree_cursor
+ : public cursor_adaptor<const_multiway_tree_cursor<Cursor>
+ , Cursor const
+ , boost::use_default
+ , bidirectional_traversal_tag
+ , descending_vertical_traversal_tag
+ > {
+ private:
+ struct enabler {};
+
+ public:
+ //TODO: Tidy up typedefs
+
+ typedef Cursor base_cursor;
+
+ typedef multiway_tree_cursor<Cursor> cursor;
+ typedef const_multiway_tree_cursor<Cursor> const_cursor;
+
+ typedef typename cursor_size<base_cursor>::type size_type;
+
+ typedef bidirectional_traversal_tag cursor_category;
+
+ typedef typename Cursor::metadata_type metadata_type;
+
+ // Container-specific:
+ typedef cursor iterator; // For (range) concepts' sake, mainly
+ typedef const_cursor const_iterator;
+
+ // Common iterator facade stuff
+ const_multiway_tree_cursor()
+ : const_multiway_tree_cursor::cursor_adaptor_() {}
+
+ explicit const_multiway_tree_cursor(base_cursor p)
+ : const_multiway_tree_cursor::cursor_adaptor_(p) {}
+
+ template <class OtherCursor>
+ const_multiway_tree_cursor(
+ const_multiway_tree_cursor<OtherCursor> const& other
+ , typename boost::enable_if<
+ boost::is_convertible<OtherCursor*,
+ typename Cursor::base_pointer> // is that correct?
+ , enabler
+ >::type = enabler()
+ )
+ : const_multiway_tree_cursor::cursor_adaptor_(other.base()) {}
+
+ operator base_cursor()
+ {
+ return this->base();
+ }
+
+ private:
+
+ friend class boost::iterator_core_access;
+
+ typename const_multiway_tree_cursor::cursor_adaptor_::reference dereference() const
+ {
+ return this->base()->m_parent->operator[](this->index());
+ }
+};
+
+template <class Cursor>
+class multiway_tree_cursor
+ : public cursor_adaptor<multiway_tree_cursor<Cursor>
+ , Cursor
+ , boost::use_default
+ , bidirectional_traversal_tag
+ , descending_vertical_traversal_tag
+ > {
+ private:
+ struct enabler {};
+ friend class cursor_core_access;
+ public:
+ //TODO: Tidy up typedefs
+
+ typedef Cursor base_cursor;
+
+ typedef multiway_tree_cursor<Cursor> cursor;
+ typedef const_multiway_tree_cursor<Cursor> const_cursor;
+
+ 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
+ multiway_tree_cursor()
+ : multiway_tree_cursor::cursor_adaptor_() {}
+
+ explicit multiway_tree_cursor(base_cursor p)
+ : multiway_tree_cursor::cursor_adaptor_(p) {}
+
+ template <class OtherCursor>
+ multiway_tree_cursor(
+ multiway_tree_cursor<OtherCursor> const& other
+ , typename boost::enable_if<
+ boost::is_convertible<OtherCursor*,
+ typename Cursor::base_pointer> // is that correct?
+ , enabler
+ >::type = enabler()
+ )
+ : multiway_tree_cursor::cursor_adaptor_(other.base()) {}
+
+ operator base_cursor()
+ {
+ return this->base();
+ }
+
+
+ private:
+
+ friend class boost::iterator_core_access;
+
+ typename multiway_tree_cursor::cursor_adaptor_::reference dereference() const
+ {
+ return this->base()->m_parent->operator[](this->index());
+ }
+
+public:
+ // Range stuff.
+// cursor begin()
+// {
+// return cursor(this->base_reference().begin());
+// }
+
+// const_cursor begin() const
+// {
+// return const_cursor(this->base_reference().begin());
+// }
+
+ // Cursor stuff.
+
+// const_cursor parent() const
+// {
+// if (!this->base_reference().index())) {
+// return this->base_reference().parent();
+// }
+// }
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_MULTIWAY_CURSOR_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,258 @@
+// 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 nary_cursor.hpp
+ * Nary cursor implementation
+ */
+
+#ifndef BOOST_TREE_DETAIL_NARY_CURSOR_HPP
+#define BOOST_TREE_DETAIL_NARY_CURSOR_HPP
+
+#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_adaptor.hpp>
+#include <boost/tree/detail/nary_node.hpp>
+
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/type_traits/is_const.hpp>
+#include <boost/type_traits/add_const.hpp>
+#include <boost/type_traits/add_pointer.hpp>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+using boost::iterator_core_access;
+using boost::tree::cursor_core_access;
+
+template <class Node>
+class ascending_nary_cursor
+ : public cursor_adaptor<ascending_nary_cursor<Node>
+ , typename mpl::eval_if<
+ is_const<Node>
+ , add_const<typename Node::base_type>
+ , mpl::identity<typename Node::base_type>
+ >::type*
+ , typename mpl::eval_if<
+ is_const<Node>
+ , add_const<typename Node::value_type>
+ , mpl::identity<typename Node::value_type>
+ >::type
+ , random_access_traversal_tag
+ , ascending_vertical_traversal_tag
+ > {
+
+private:
+ typedef typename Node::base_type node_base;
+
+ typedef typename mpl::eval_if<
+ is_const<Node>
+ , add_const<node_base>
+ , mpl::identity<node_base>
+ >::type base_type;
+
+ typedef base_type* base_pointer;
+
+ struct enabler {};
+
+ typedef Node node_type;
+ typedef node_type* node_pointer;
+
+public:
+ typedef typename mpl::eval_if<
+ is_const<Node>
+ , add_const<typename Node::value_type>
+ , mpl::identity<typename Node::value_type>
+ >::type value_type;
+
+ // Container-specific:
+ typedef typename ascending_nary_cursor::cursor_adaptor_::size_type size_type;
+
+ // Cursor-specific
+ typedef ascending_nary_cursor<node_type> cursor;
+ typedef ascending_nary_cursor<node_type const> const_cursor;
+ typedef std::size_t subtree_size_type;
+
+ // Container-specific:
+ typedef cursor iterator;
+ typedef const_cursor const_iterator;
+
+ template <class OtherValue>
+ struct rebind {
+ typedef ascending_nary_cursor<OtherValue> other;
+ };
+
+ ascending_nary_cursor()
+ : ascending_nary_cursor::cursor_adaptor_(0), m_pos(0) {}
+
+ explicit ascending_nary_cursor(base_pointer p, size_type pos)
+ : ascending_nary_cursor::cursor_adaptor_(p), m_pos(pos) {}
+
+ template <class OtherNode>
+ ascending_nary_cursor(
+ ascending_nary_cursor<OtherNode> const& other
+ , typename boost::enable_if<
+ boost::is_convertible<OtherNode*, node_type*>
+ , enabler
+ >::type = enabler()
+ )
+ : ascending_nary_cursor::cursor_adaptor_(other.base()), m_pos(other.m_pos) {}
+
+ size_type m_pos;
+
+private:
+
+ friend class iterator_core_access;
+ friend class cursor_core_access;
+
+ friend class access_detach;
+
+ value_type& dereference() const
+ {
+ return **static_cast<node_type*>(this->base_reference());
+ }
+
+ bool equal(cursor const& other) const
+ {
+ return (this->base_reference() == other.base_reference()) && (this->m_pos == other.m_pos);
+ }
+
+ void increment()
+ {
+ ++m_pos;
+ // this->base_reference() += sizeof(node_type);
+ }
+
+ void decrement()
+ {
+ --m_pos;
+ //this->base_reference() -= sizeof(node_type);
+ }
+
+ void advance(typename ascending_nary_cursor::cursor_facade_::difference_type n)
+ {
+ m_pos += n;
+ //this->base_reference() += n * sizeof(node_type);
+ }
+
+ typename ascending_nary_cursor::cursor_facade_::difference_type
+ distance_to(ascending_nary_cursor z) const //FIXME: convertible to instead of ascending_nary_cursor
+ {
+ return (z.m_pos - this->m_pos);
+ //return (z.base_reference() - this->base_reference()) / sizeof(node_type);
+ }
+
+ // Container specific
+ bool empty_() const
+ {
+ return this->base_reference()->m_children[m_pos] == node_type::nil(); //->empty();
+ //return this->base_reference()->get_index();
+ }
+
+ size_type size_() const
+ {
+ return this->base_reference()->m_children.size();
+ }
+
+ size_type max_size_() const
+ {
+ return this->base_reference()->m_children.max_size();
+ }
+
+ size_type idx() const
+ {
+ return m_pos;
+ //return
+ }
+
+ void left()
+ {
+ this->base_reference() = this->base_reference()->m_children[m_pos];
+ m_pos = 0;
+ //this->base_reference() = this->base_reference()->operator[0];
+ }
+
+ void right()
+ {
+ size_type new_pos = this->base_reference()->m_children.size()-1;
+ this->base_reference() = this->base_reference()->m_children[m_pos];
+ m_pos = new_pos;
+ //this->base_reference() = this->base_reference()->operator[0];
+ }
+
+ // Cursor stuff
+ void up()
+ {
+ m_pos = this->base_reference()->get_index();
+ this->base_reference() = static_cast<base_pointer>(this->base_reference()->parent());
+ //this->base_reference() = this->base_reference()->parent();
+ }
+
+protected:
+ bool is_on_top() const
+ {
+ base_pointer parent_begin_node =
+ static_cast<base_pointer>(this->base_reference()->parent())
+ ->m_children[this->base_reference()->get_index()];
+ return (!m_pos && (this->base_reference() != parent_begin_node));
+ // (*this != this->parent().begin())
+ }
+
+public:
+
+ base_pointer const& base_node() const
+ {
+ return this->base_reference();
+ }
+
+ base_pointer& base_node()
+ {
+ return this->base_reference();
+ }
+
+ // TODO: protect?
+ void attach(node_pointer p_node)
+ {
+ p_node->m_parent = this->base_reference();
+
+ // Only forest-relevant:
+// p_node->operator[](1) = this->base_reference()->operator[](m_pos);
+// this->base_reference()->operator[](m_pos)->m_parent = p_node;
+
+ this->base_reference()->m_children[m_pos] = p_node;
+ }
+
+// /**
+// * Detaches the node this cursor points to and returns a pointer to it;
+// * this cursor will be set to its inorder successor afterwards (?)
+// */
+// node_pointer detach()
+// {
+// return static_cast<node_pointer>(m_node->detach(m_pos));
+// }
+//
+// node_pointer detach(cursor y)
+// {
+// return static_cast<node_pointer>(m_node->detach(m_pos, y.m_pos, y.m_node));
+// }
+
+};
+
+} // namespace detail
+
+template <class Node>
+typename detail::ascending_nary_cursor<Node>::size_type
+index(detail::ascending_nary_cursor<Node> const& cur)
+{
+ return cur.index();
+}
+
+} // namespace tree
+} // namespace boost
+
+
+#endif // BOOST_TREE_DETAIL_NARY_CURSOR_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,262 @@
+// 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 nary_node.hpp
+ * Nary node implementation (with N=2, i.e. binary specialization)
+ */
+
+//Templatize with arity (so we can use this for multiway trees, too?)
+
+#ifndef BOOST_TREE_DETAIL_NARY_NODE_HPP
+#define BOOST_TREE_DETAIL_NARY_NODE_HPP
+
+#include <boost/array.hpp>
+
+#include <iterator>
+#include <utility>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+using boost::array;
+
+//template <class T> struct binary_array : public array<T, 2> { };
+
+//struct node_base;
+/*
+ * node_with_parent_base
+ */
+
+class node_with_parent_base {
+// typedef node_with_parent_base self_type;
+// typedef self_type* base_pointer;
+// typedef self_type const* const_base_pointer;
+
+public:
+ node_with_parent_base* m_parent; // TODO: protect?
+
+ node_with_parent_base()
+ {
+ m_parent = this;
+ }
+
+ node_with_parent_base(node_with_parent_base* p) : m_parent(p) {}
+
+ node_with_parent_base* parent()
+ {
+ return m_parent;
+ }
+
+ node_with_parent_base* const parent() const
+ {
+ return m_parent;
+ }
+};
+
+//template <template <typename> class Container>
+//class node_base;
+//
+//template <template <typename> class Container>
+//class node_base : public node_with_parent_base, public Container<node_base<Container>*> {
+// typedef node_base<Container> self_type;
+//
+//public:
+//
+// typedef Container<node_base<Container>*> base_type;
+// typedef typename base_type::size_type size_type;
+// typedef self_type* base_pointer;
+// typedef self_type const* const_base_pointer;
+//
+// node_base() : node_with_parent_base()
+// { }
+//
+// static base_pointer nil()
+// {
+// static self_type m_nil_obj;
+// static base_pointer m_nil = &m_nil_obj;
+// return m_nil;
+// }
+//
+// void init()
+// {
+// for (typename base_type::size_type i=0; i<base_type::size(); ++i)
+// operator[](i) = nil();
+// }
+//
+// // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
+// bool const empty() const
+// {
+// return ((this == nil()) || this->base_type::empty());
+// }
+//
+// // O(n); n is number of parent's children
+// typename base_type::size_type const get_index() const
+// {
+// typename base_type::size_type i = 0;
+// while (static_cast<base_pointer>(this->m_parent)->base_type::operator[](i++) != this);
+// return --i;
+// //return (static_cast<base_pointer>(this->m_parent)->base_type::operator[](0) == this ? 0 : 1);
+// }
+//};
+
+class node_base;
+
+class node_with_children_base {
+public:
+ typedef array<node_base*, 2> children_type;
+
+//protected:
+ children_type m_children;
+};
+
+class node_base
+: public node_with_parent_base, public node_with_children_base {
+ typedef node_base self_type;
+
+public:
+ //typedef node_with_children_base::base_type base_type;
+ typedef self_type* base_pointer;
+ typedef self_type const* const_base_pointer;
+
+ node_base() : node_with_parent_base(), node_with_children_base()
+ { }
+
+ node_base(node_with_parent_base* p)
+ : node_with_parent_base(p), node_with_children_base()
+ { }
+
+ static base_pointer nil()
+ {
+ static self_type m_nil_obj;
+ static base_pointer m_nil = &m_nil_obj;
+ return m_nil;
+ }
+
+ void init()
+ {
+ for (children_type::size_type i=0; i<children_type::max_size(); ++i)
+ m_children[i] = nil();
+ }
+
+ // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
+// bool const empty() const
+// {
+// return (this == nil());
+// }
+
+ // Binary specific
+
+ children_type::size_type rotate(children_type::size_type const& c)
+ {
+ //TODO: Optimise.
+ base_pointer q = m_children[c];
+
+ base_pointer B = m_children[c]->m_children[(c ? 0 : 1)];
+ //pre_rotate();
+
+ //B swaps places with its m_parent:
+
+ m_children[c] = B;
+ B->m_parent = this;
+ q->m_parent = this->m_parent;
+
+ children_type::size_type qp = get_index();
+ static_cast<base_pointer>(q->m_parent)->m_children[qp] = q;
+ this->m_parent = q;
+ q->m_children[(c ? 0 : 1)] = this;
+ return qp;
+ //return (c ? 0 : 1);
+ }
+
+ base_pointer detach(children_type::size_type m_pos)
+ {
+ base_pointer q = m_children[m_pos];
+ m_children[m_pos] =
+ m_children[m_pos]
+ ->m_children[((m_children[m_pos])
+ ->m_children[0] == node_base::nil() ? 1 : 0)];
+ m_children[m_pos]->m_parent = this;
+ return q;
+ }
+
+ // TODO: actually implement this.
+ base_pointer detach(children_type::size_type index,
+ children_type::size_type other_index,
+ base_pointer other)
+ {
+ //Node::pre_splice(q, r);
+ // splice out q
+ base_pointer x = detach(index);
+
+ // q has been spliced out, now relink it in place of r.
+ static_cast<base_pointer>(other->m_parent)->m_children[other_index] = this;
+ m_parent = other->m_parent;
+
+ for (children_type::size_type i=0; i<children_type::max_size(); ++i) {
+ m_children[i] = other->m_children[i];
+ m_children[i]->m_parent = this;
+ }
+ return x;
+ }
+
+ // O(1)
+ children_type::size_type const get_index() const
+ {
+ return (static_cast<base_pointer>(this->m_parent)->m_children[0] == this ? 0 : 1);
+ }
+
+};
+
+class descending_node_base
+: public node_with_children_base {
+};
+
+template <typename T>
+class ascending_node : public node_base {
+ public:
+ typedef T value_type;
+
+ typedef ascending_node<value_type> node_type;
+ typedef node_type* node_pointer;
+ typedef node_type& node_reference;
+
+ typedef node_base base_type;
+ typedef base_type* base_pointer;
+ typedef base_type const* const_base_pointer;
+
+ typedef value_type& reference;
+ typedef value_type const& const_reference;
+ typedef value_type* pointer;
+
+ //enum size_t { first = 0, second = 1 };
+ //typedef std::size_t size_type;
+
+ // TODO: add observers.
+
+ reference operator*() { return *m_data; }
+
+ const_reference operator*() const { return *m_data; }
+
+ ascending_node(pointer data) : base_type(), m_data(data) {}
+
+ ascending_node(pointer data, base_pointer p) : base_type(p), m_data(data) {}
+
+ pointer data()
+ {
+ return m_data;
+ }
+
+ private:
+ pointer m_data;
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_NARY_NODE_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/node_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/node_traits.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,40 @@
+// 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)
+
+#ifndef BOOST_TREE_DETAIL_NODE_TRAITS_HPP
+#define BOOST_TREE_DETAIL_NODE_TRAITS_HPP
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+template <class Node>
+struct node_traits
+{
+ typedef Node node_type;
+
+ // Value
+ typedef typename node_type::value_type value_type;
+ typedef typename node_type::pointer pointer;
+ typedef typename node_type::reference reference;
+ //typedef typename node_type::size_type size_type;
+
+ // Node
+ typedef typename node_type::node_pointer node_pointer;
+ typedef typename node_type::node_reference node_reference;
+
+ // Node base
+ typedef typename node_type::base_type node_base_type;
+ typedef typename node_type::base_pointer node_base_pointer;
+
+ typedef node_base_pointer position_type;
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_NODE_TRAITS_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -12,7 +12,7 @@
#ifndef BOOST_TREE_FOREST_TREE_HPP
#define BOOST_TREE_FOREST_TREE_HPP
-#include <boost/tree/detail/cursor/forest.hpp>
+#include <boost/tree/detail/forest_cursor.hpp>
#include <boost/tree/binary_tree.hpp>
#include <boost/tree/algorithm.hpp>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -16,7 +16,7 @@
//#include <boost/tree/cursor.hpp>
//#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/detail/cursor/multiway.hpp>
+#include <boost/tree/detail/multiway_cursor.hpp>
#include <boost/tree/nary_tree.hpp>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -15,8 +15,8 @@
#include <boost/tree/cursor.hpp>
-#include <boost/tree/detail/node/traits.hpp>
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/node_traits.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <memory>
#include <vector>
@@ -65,9 +65,9 @@
typedef ascending_node<value_type/*, mycontainer*/> node_type;
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
- typedef typename node_traits<node_type>::node_base_type node_base_type;
+ typedef typename detail::node_traits<node_type>::node_base_type node_base_type;
typedef node_base_type* node_base_pointer;
- typedef typename node_traits<node_type>::node_pointer node_pointer;
+ typedef typename detail::node_traits<node_type>::node_pointer node_pointer;
typedef ascending_nary_cursor<node_type> cursor;
typedef ascending_nary_cursor<node_type const> const_cursor;