Subject: [Boost-commit] svn:boost r85025 - sandbox/tree_node/boost/tree_node/balancer
From: sponage_at_[hidden]
Date: 2013-07-13 14:07:24
Author: expaler
Date: 2013-07-13 14:07:24 EDT (Sat, 13 Jul 2013)
New Revision: 85025
URL: http://svn.boost.org/trac/boost/changeset/85025
Log:
Boost.TreeNode: fixed bug in AVL balancer.
Replaced:
sandbox/tree_node/boost/tree_node/balancer/adelson_velskii_landis.hpp (contents, props changed)
Added: sandbox/tree_node/boost/tree_node/balancer/adelson_velskii_landis.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ sandbox/tree_node/boost/tree_node/balancer/adelson_velskii_landis.hpp 2013-07-13 14:07:24 EDT (Sat, 13 Jul 2013) (r85025)
@@ -0,0 +1,218 @@
+// Copyright (C) 2013 Cromwell D. Enage
+// 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_NODE_BALANCER_ADELSON_VELSKII_LANDIS_HPP_INCLUDED
+#define BOOST_TREE_NODE_BALANCER_ADELSON_VELSKII_LANDIS_HPP_INCLUDED
+
+//[reference__adelson_velskii_landis_balancer
+namespace boost { namespace tree_node {
+
+ struct adelson_velskii_landis_balancer
+ {
+ template <typename Node, typename Size>
+ static void post_fill(Node& root, Size n);
+
+ template <typename NodePointer>
+ static NodePointer post_insert(NodePointer node_ptr);
+
+ template <typename Node>
+ static bool choose_predecessor(Node const& node);
+
+ template <typename Node>
+ static bool pre_erase(Node const& node);
+
+ template <typename NodePointer>
+ static NodePointer post_erase_left(NodePointer node_ptr);
+
+ template <typename NodePointer>
+ static NodePointer post_erase_right(NodePointer node_ptr);
+
+ //<-
+ private:
+ template <typename NodePointer>
+ static NodePointer _balance(NodePointer node_ptr);
+ //->
+ };
+
+ namespace balancer {
+
+ typedef ::boost::tree_node::adelson_velskii_landis_balancer
+ adelson_velskii_landis;
+ } // namespace balancer
+}} // namespace boost::tree_node
+//]
+
+#include <boost/tree_node/key/height.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename Size>
+ inline void
+ adelson_velskii_landis_balancer::post_fill(Node& root, Size n)
+ {
+ }
+
+ template <typename NodePointer>
+ inline NodePointer
+ adelson_velskii_landis_balancer::post_insert(NodePointer node_ptr)
+ {
+ return adelson_velskii_landis_balancer::_balance(node_ptr);
+ }
+
+ template <typename Node>
+ inline bool
+ adelson_velskii_landis_balancer::choose_predecessor(Node const& node)
+ {
+ return get(*node.get_right_child_ptr(), height_key()) < get(
+ *node.get_left_child_ptr()
+ , height_key()
+ );
+ }
+
+ template <typename Node>
+ inline bool adelson_velskii_landis_balancer::pre_erase(Node const& node)
+ {
+ return true;
+ }
+
+ template <typename NodePointer>
+ inline NodePointer
+ adelson_velskii_landis_balancer::post_erase_left(NodePointer node_ptr)
+ {
+ if (
+ node_ptr->get_right_child_ptr() && get(
+ *node_ptr->get_right_child_ptr()
+ , height_key()
+ )
+ )
+ {
+ return node_ptr->rotate_left();
+ }
+ else
+ {
+ return adelson_velskii_landis_balancer::_balance(node_ptr);
+ }
+ }
+
+ template <typename NodePointer>
+ inline NodePointer
+ adelson_velskii_landis_balancer::post_erase_right(NodePointer node_ptr)
+ {
+ if (
+ node_ptr->get_left_child_ptr() && get(
+ *node_ptr->get_left_child_ptr()
+ , height_key()
+ )
+ )
+ {
+ return node_ptr->rotate_right();
+ }
+ else
+ {
+ return adelson_velskii_landis_balancer::_balance(node_ptr);
+ }
+ }
+
+ template <typename NodePointer>
+ NodePointer adelson_velskii_landis_balancer::_balance(NodePointer node_ptr)
+ {
+ NodePointer grandparent_ptr;
+
+ for (
+ NodePointer parent_ptr;
+ (parent_ptr = node_ptr->get_parent_ptr()) && (
+ grandparent_ptr = parent_ptr->get_parent_ptr()
+ );
+ node_ptr = parent_ptr
+ )
+ {
+ if (
+ !grandparent_ptr->get_left_child_ptr() || (
+ grandparent_ptr->get_right_child_ptr() && (
+ 1 + get(
+ *grandparent_ptr->get_left_child_ptr()
+ , height_key()
+ ) < get(
+ *grandparent_ptr->get_right_child_ptr()
+ , height_key()
+ )
+ )
+ )
+ )
+ {
+ parent_ptr = grandparent_ptr->get_right_child_ptr();
+
+ if (
+ !parent_ptr->get_right_child_ptr() || (
+ parent_ptr->get_left_child_ptr() && (
+ get(
+ *parent_ptr->get_right_child_ptr()
+ , height_key()
+ ) < get(
+ *parent_ptr->get_left_child_ptr()
+ , height_key()
+ )
+ )
+ )
+ )
+ {
+ parent_ptr = parent_ptr->rotate_right();
+ }
+
+ grandparent_ptr = grandparent_ptr->rotate_left();
+
+ if (!grandparent_ptr->get_parent_ptr())
+ {
+ return grandparent_ptr;
+ }
+ }
+ else if (
+ !grandparent_ptr->get_right_child_ptr() || (
+ grandparent_ptr->get_left_child_ptr() && (
+ 1 + get(
+ *grandparent_ptr->get_right_child_ptr()
+ , height_key()
+ ) < get(
+ *grandparent_ptr->get_left_child_ptr()
+ , height_key()
+ )
+ )
+ )
+ )
+ {
+ parent_ptr = grandparent_ptr->get_left_child_ptr();
+
+ if (
+ !parent_ptr->get_left_child_ptr() || (
+ parent_ptr->get_right_child_ptr() && (
+ get(
+ *parent_ptr->get_left_child_ptr()
+ , height_key()
+ ) < get(
+ *parent_ptr->get_right_child_ptr()
+ , height_key()
+ )
+ )
+ )
+ )
+ {
+ parent_ptr = parent_ptr->rotate_left();
+ }
+
+ grandparent_ptr = grandparent_ptr->rotate_right();
+
+ if (!grandparent_ptr->get_parent_ptr())
+ {
+ return grandparent_ptr;
+ }
+ }
+ }
+
+ return node_ptr;
+ }
+}} // namespace boost::tree_node
+
+#endif // BOOST_TREE_NODE_BALANCER_ADELSON_VELSKII_LANDIS_HPP_INCLUDED
+