|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49677 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm boost/tree/detail/augmentors boost/tree/detail/balancers boost/tree/detail/cursor libs/tree/doc/html libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-10 13:43:23
Author: bernhard.reiter
Date: 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
New Revision: 49677
URL: http://svn.boost.org/trac/boost/changeset/49677
Log:
More fixes regarding index(), and removal of root_tracking_cursor around OutCursor in iterative transform.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 2
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 53 ++++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/coupling_cursor.hpp | 9 ++++++
sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp | 7 +++++
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp | 3 +
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp | 6 ++--
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp | 12 ++++----
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp | 14 +++------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp | 6 ++--
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp | 6 ++--
sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/rank.hpp | 8 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp | 12 +++++++-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 3 +
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp | 7 +++++
sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html | 14 +++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 4 +-
23 files changed, 132 insertions(+), 52 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -90,7 +90,6 @@
pp. 348--351). Those should be especially useful for automated testing of "real" (binary,
forest) trees.
* have `erase()` operations return cursor/iterator instead of void (as in new STD)
-* modify parity/parent specs according to newsgroup thread, but add members to binary_tree cursor!
* We might need still more binary_tree members for more efficient functions operating on
ranges...
* `insert()` and `erase()` semantics need reworking. For instance, Proposal 23.X.4.1.4 §2
@@ -118,6 +117,7 @@
Proposal:
+* Change parity/parent complexity requirements at least for binary_tree::cursor? - See newsgroup thread.
* Change complexity requirements for * order end() to constant? We're using root(), and
for postorder begin() - which is also root() - it's already constant. Then again, how much
do we cater for "pathological" implementations (and not so pathological ones, like
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -149,7 +149,7 @@
size_type const idx() const
{
- return m_s.top().index();
+ return index(m_s.top());
}
void left()
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-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -80,6 +80,7 @@
typedef typename augmented_type<Val,Meta,Meta2>::metadata_type type;
};
+
template <class Cursor>
class is_on_top_cursor
: public Cursor {
@@ -96,6 +97,58 @@
}
};
+//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> > {
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 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -480,7 +480,7 @@
static_cast<node_base_pointer>(p_node->m_parent)
->node_base_type::operator[](0) = (*p_node)[0];
- while (position.index())
+ while (index(position))
position = position.parent();
} else {
position = position.begin();
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/coupling_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/coupling_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/coupling_cursor.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -116,13 +116,20 @@
}
};
+template <class InCursor, class OutCursor>
+typename coupling_cursor<InCursor, OutCursor>::size_type
+index(coupling_cursor<InCursor, OutCursor> const& cur)
+{
+ return cur.index();
+}
+
/**
* @param o An output iterator.
* @result An instance of coupling_cursor working on o.
*
* Use as shortcut for cumbersome typenames, just as with std::inserter and the like.
*/
-template<class InCursor, class OutCursor>
+template <class InCursor, class OutCursor>
inline coupling_cursor<InCursor, OutCursor>
make_coupling_cursor(InCursor i, OutCursor o)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -237,6 +237,13 @@
std::size_t const index() const { return 0; }
};
+template <class OutputIterator>
+typename output_cursor_iterator_wrapper<OutputIterator>::size_type
+index(output_cursor_iterator_wrapper<OutputIterator> const& cur)
+{
+ return cur.index();
+}
+
/**
* @param o An output iterator.
* @result An instance of output_cursor_iterator_wrapper working on o.
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -144,6 +144,7 @@
typedef typename cursor_facade_::horizontal_traversal horizontal_traversal;
typedef typename cursor_facade_::vertical_traversal cursor_category;
+ typedef typename cursor_facade_::difference_type difference_type;
typedef typename cursor_facade_::size_type size_type;
cursor_adaptor() {}
@@ -180,7 +181,7 @@
template <class OtherDerived, class OtherCursor, class V, class C,
class R, class D, class S>
- Difference distance_to(cursor_adaptor<OtherDerived, OtherCursor,
+ difference_type distance_to(cursor_adaptor<OtherDerived, OtherCursor,
V, C, R, D, S> const& x) const
{
return x.base() - m_cursor;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -156,7 +156,7 @@
return this->derived();
}
- Derived begin()
+ Derived begin() const
{
Derived tmp(this->derived());
return tmp.to_begin();
@@ -168,7 +168,7 @@
return this->derived();
}
- Derived end()
+ Derived end() const
{
Derived tmp(this->derived());
return tmp.to_end();
@@ -180,7 +180,7 @@
return this->derived();
}
- Derived parent()
+ Derived parent() const
{
Derived tmp(this->derived());
return tmp.to_parent();
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -40,7 +40,7 @@
return;
}
- while (c.index() && !c.is_root())
+ while (index(c) && !c.is_root())
c.to_parent();
return;
}
@@ -58,7 +58,7 @@
return;
}
- while (!c.index() && !c.is_root())
+ while (!index(c) && !c.is_root())
c.to_parent();
if (!c.is_root())
--c;
@@ -196,7 +196,7 @@
MultiwayCursor y = x;
while (!x.empty()) {
x = std::lower_bound(x.begin(), x.end(), val);
- if (x.index() == 0)
+ if (index(x) == 0)
y = x;
}
return y;
@@ -221,7 +221,7 @@
MultiwayCursor y = x;
while (!x.empty()) {
x = std::lower_bound(x.begin(), x.end(), val, cmp);
- if (x.index() == 0)
+ if (index(x) == 0)
y = x;
}
return y;
@@ -245,7 +245,7 @@
MultiwayCursor y = x;
while (!x.empty()) {
x = std::upper_bound(x.begin(), x.end(), val);
- if (x.index() == 0)
+ if (index(x) == 0)
y = x;
}
return y;
@@ -270,7 +270,7 @@
MultiwayCursor y = x;
while (!x.empty()) {
x = std::upper_bound(x.begin(), x.end(), val, cmp);
- if (x.index() == 0)
+ if (index(x) == 0)
y = x;
}
return y;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -43,14 +43,13 @@
}
template <class Order, class InCursor, class OutCursor, class Op>
-root_tracking_cursor<OutCursor> transform (Order
- , root_tracking_cursor<InCursor> s
- , root_tracking_cursor<OutCursor> t
- , Op op)
+OutCursor transform (Order, root_tracking_cursor<InCursor> s
+ , OutCursor t
+ , Op op)
{
root_tracking_cursor<InCursor> s2(s);
- boost::tree::coupling_cursor< root_tracking_cursor<InCursor>, root_tracking_cursor<OutCursor> > cc(s, t);
+ boost::tree::coupling_cursor< root_tracking_cursor<InCursor>, OutCursor > cc(s, t);
to_first(Order(), cc);
to_last(Order(), s2);
@@ -66,10 +65,7 @@
OutCursor transform (Order, InCursor s, OutCursor t, Op op
, bidirectional_traversal_tag)
{
- root_tracking_cursor<OutCursor> u
- = transform(Order(), root_tracking_cursor<InCursor>(s)
- , root_tracking_cursor<OutCursor>(t), op);
- return u.base();
+ return transform(Order(), root_tracking_cursor<InCursor>(s), t, op);
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -37,7 +37,7 @@
if (c.is_root())
return;
- if (c.index()) { // Right child? Return parent.
+ if (index(c)) { // Right child? Return parent.
--c;
return;
}
@@ -49,7 +49,7 @@
if (c.empty())
++c;
}
- if (c.index())
+ if (index(c))
--c;
return;
}
@@ -79,7 +79,7 @@
// child (which is what we'll return) or we land at root.
while (!c.is_root()) {
c.to_parent();
- if (c.index())
+ if (index(c))
if (!(--c).empty()) {
c.to_begin();
return;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -53,7 +53,7 @@
// we find an ancestor that has a right child.
while (!c.is_root()) { // Doesn't work with subtrees!
c.to_parent();
- if (!c.is_root() && !c.index()) {
+ if (!c.is_root() && !index(c)) {
if (!(++c).empty()) {
c.to_begin();
return;
@@ -74,7 +74,7 @@
c.to_parent();
// If a left child was given, just move to its parent.
- if (!c.index())
+ if (!index(c))
return;
// So this is a right child.
@@ -88,7 +88,7 @@
else
c.to_begin();
- if (c.index())
+ if (index(c))
--c;
return;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/rank.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/rank.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmentors/rank.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -61,7 +61,7 @@
void pre_rotate(Tree&, typename Tree::cursor& q)
{
typename Tree::cursor p = q->parent();
- if (!q.index())
+ if (!index(q))
p.metadata().rank() -= q.metadata().rank();
else
q.metadata().rank() += p.metadata().rank();
@@ -72,7 +72,7 @@
{
typename Tree::cursor p = y;
while (p.parent() != t.root()) {
- if (!p.index())
+ if (!index(p))
--p.parent().metadata().rank();
p = p.parent();
}
@@ -83,7 +83,7 @@
{
typename Tree::cursor p = y;
while (p.parent() != t.root()) {
- if (!p.index())
+ if (!index(p))
--p.parent().metadata().rank();
p = p.parent();
}
@@ -94,7 +94,7 @@
template <class Tree>
void descend(Tree&, typename Tree::cursor& p)
{
- if (p.index() == 0) {
+ if (index(p) == 0) {
++p.metadata().rank();
}
}
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 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -55,9 +55,9 @@
y->metadata().set_color(black);
x = x.parent().parent();
} else {
- if (x.index() != x.parent().index()) {
+ if (index(x) != index(x.parent())) {
t.rotate(x);
- x = (x.index() ? x.end() : x.begin());
+ x = (index(x) ? x.end() : x.begin());
}
x.parent()->metadata().set_color(black);
x.parent().parent()->metadata().set_color(red);
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -102,7 +102,7 @@
void decrement()
{
- if (!this->base().index())
+ if (!index(this->base()))
this->base_reference().to_parent();
--this->base_reference();
}
@@ -120,12 +120,20 @@
void up()
{
- if (!this->base().index())
+ if (!index(this->base()))
this->base_reference().to_parent();
}
};
} // namespace detail
+
+template <class Cursor>
+typename detail::forest_cursor<Cursor>::size_type
+index(detail::forest_cursor<Cursor> const& cur)
+{
+ return cur.index();
+}
+
} // namespace tree
} // namespace boost
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 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -231,7 +231,8 @@
} // namespace detail
template <class Node>
-typename detail::nary_tree_cursor<Node>::size_type index(detail::nary_tree_cursor<Node> const& cur)
+typename detail::nary_tree_cursor<Node>::size_type
+index(detail::nary_tree_cursor<Node> const& cur)
{
return cur.index();
}
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 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -95,7 +95,7 @@
base_cursor bc = base_cursor(pos);
if (bc != h.root())
bc = bc.parent();
- //if (bc.index())
+ //if (index(bc))
return cursor(h.insert(bc, val));
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -67,7 +67,7 @@
typename insert_cursor::cursor_adaptor_::reference dereference() const
{
- if (this->base_reference().index()) {
+ if (index(this->base_reference())) {
const_cast<typename Tree::cursor&>(this->base_reference())
= tree.insert(this->base_reference(), typename Tree::value_type());
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -63,13 +63,13 @@
void increment()
{
forward(Order(), this->base_reference());
- //BOOST_ASSERT(!this->base_reference().index() || this->base_reference().is_root());
+ //BOOST_ASSERT(!index(this->base_reference()) || this->base_reference().is_root());
}
void decrement()
{
back(Order(), this->base_reference());
- //BOOST_ASSERT(!this->base_reference().index() || this->base_reference().is_root());
+ //BOOST_ASSERT(!index(this->base_reference()) || this->base_reference().is_root());
}
};
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 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -129,7 +129,7 @@
bc.m_pos = 0;
}
else {
- bc->insert((bc->begin()+bc.index()), val);
+ bc->insert((bc->begin()+index(bc)), val);
}
return cursor(bc);
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -107,6 +107,13 @@
};
template <class Cursor>
+typename root_tracking_cursor<Cursor>::size_type
+index(root_tracking_cursor<Cursor> const& cur)
+{
+ return cur.index();
+}
+
+template <class Cursor>
inline root_tracking_cursor<Cursor> track_root(Cursor c)
{
return root_tracking_cursor<Cursor>(c);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -1268,20 +1268,20 @@
<li>
<p><strong>Effects:</strong> Performs a left tree rotation around the
- parent of <tt>position</tt> if <tt>position.parity() == 0</tt> or a
- right tree rotation if <tt>position.parity() == 1</tt>.</p>
+ parent of <tt>position</tt> if <tt>position.index() == 0</tt> or a
+ right tree rotation if <tt>position.index() == 1</tt>.</p>
</li>
<li>
<p><strong>Postcondition:</strong> If <tt>par ==
- position.parity()</tt> as of before the rotation, then, after the
+ position.index()</tt> as of before the rotation, then, after the
rotation:</p>
<ul>
<li><tt>*position.begin()</tt> yields the same value it yielded
before the rotation</li>
- <li><tt>position.parity() == !par</tt></li>
+ <li><tt>position.index() == !par</tt></li>
<li><tt>*(((position.begin())[par]).begin())</tt> yields what
<tt>*(p.begin())</tt> yielded before, if <tt>p</tt> was
@@ -1837,7 +1837,7 @@
<tr>
<td><tt>!f</tt></td>
- <td><tt>while ((!b).parity() == 1); b =
+ <td><tt>while ((!b).index() == 1); b =
(!b).begin();</tt><br /></td>
<td>linear</td>
@@ -2081,7 +2081,7 @@
<tr>
<td><tt>*m</tt></td>
- <td><tt>*((p->begin())[b.parity()])</tt></td>
+ <td><tt>*((p->begin())[b.index()])</tt></td>
<td>constant</td>
</tr>
@@ -3153,7 +3153,7 @@
</tr>
<tr>
- <td><tt>a.parity()</tt></td>
+ <td><tt>a.index()</tt></td>
<td><tt>size_type</tt></td>
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp 2008-11-10 13:43:21 EST (Mon, 10 Nov 2008)
@@ -49,7 +49,7 @@
c3 = c1.end();
BOOST_CHECK(c3 == c1.end());
--c3;
- BOOST_CHECK_EQUAL(c3.index(), 0);
+ BOOST_CHECK_EQUAL(index(c3), 0);
BOOST_CHECK(c3.parent() != c3);
BOOST_CHECK(c3.parent() == c1);
BOOST_CHECK(c3 == c1.begin());
@@ -230,7 +230,7 @@
BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
- BOOST_CHECK_EQUAL(c.index(), 1);
+ BOOST_CHECK_EQUAL(index(c), 1);
BOOST_CHECK_EQUAL(*c.begin(), 6);
bt.rotate(c); // Left rotate
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk