diff options
Diffstat (limited to 'boost/heap/fibonacci_heap.hpp')
| -rw-r--r-- | boost/heap/fibonacci_heap.hpp | 86 |
1 files changed, 46 insertions, 40 deletions
diff --git a/boost/heap/fibonacci_heap.hpp b/boost/heap/fibonacci_heap.hpp index 76d1cfae65..9432276777 100644 --- a/boost/heap/fibonacci_heap.hpp +++ b/boost/heap/fibonacci_heap.hpp @@ -10,6 +10,7 @@ #define BOOST_HEAP_FIBONACCI_HEAP_HPP #include <algorithm> +#include <utility> #include <vector> #include <boost/array.hpp> @@ -20,6 +21,11 @@ #include <boost/heap/detail/stable_heap.hpp> #include <boost/heap/detail/tree_iterator.hpp> +#ifdef BOOST_HAS_PRAGMA_ONCE +#pragma once +#endif + + #ifndef BOOST_DOXYGEN_INVOKED #ifdef BOOST_HEAP_SANITYCHECKS #define BOOST_HEAP_ASSERT BOOST_ASSERT @@ -62,30 +68,30 @@ struct make_fibonacci_heap_base base_type(arg) {} -#ifdef BOOST_HAS_RVALUE_REFS + type(type const & rhs): + base_type(static_cast<base_type const &>(rhs)), + allocator_type(static_cast<allocator_type const &>(rhs)) + {} + + type & operator=(type const & rhs) + { + base_type::operator=(static_cast<base_type const &>(rhs)); + allocator_type::operator=(static_cast<allocator_type const &>(rhs)); + return *this; + } + +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES type(type && rhs): base_type(std::move(static_cast<base_type&>(rhs))), allocator_type(std::move(static_cast<allocator_type&>(rhs))) {} - type(type & rhs): - base_type(static_cast<base_type&>(rhs)), - allocator_type(static_cast<allocator_type&>(rhs)) - {} - type & operator=(type && rhs) { base_type::operator=(std::move(static_cast<base_type&>(rhs))); allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs))); return *this; } - - type & operator=(type const & rhs) - { - base_type::operator=(static_cast<base_type const &>(rhs)); - allocator_type::operator=(static_cast<allocator_type const &>(rhs)); - return *this; - } #endif }; }; @@ -228,7 +234,7 @@ public: size_holder::set_size(rhs.size()); } -#ifdef BOOST_HAS_RVALUE_REFS +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) fibonacci_heap(fibonacci_heap && rhs): super_t(std::move(rhs)), top_element(rhs.top_element) @@ -358,7 +364,7 @@ public: return handle_type(n); } -#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES) +#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) /** * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element. * @@ -396,16 +402,7 @@ public: node_pointer element = top_element; roots.erase(node_list_type::s_iterator_to(*element)); - add_children_to_root(element); - - element->~node(); - allocator_type::deallocate(element, 1); - - size_holder::decrement(); - if (!empty()) - consolidate(); - else - top_element = NULL; + finish_erase_or_pop(element); } /** @@ -425,7 +422,7 @@ public: /** \copydoc boost::heap::fibonacci_heap::update(handle_type, const_reference) * * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates - * the iterator the the object referred to by the handle. + * the iterator to the object referred to by the handle. * */ void update_lazy(handle_type handle, const_reference v) { @@ -456,7 +453,7 @@ public: /** \copydoc boost::heap::fibonacci_heap::update (handle_type handle) * * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates - * the iterator the the object referred to by the handle. + * the iterator to the object referred to by the handle. * */ void update_lazy (handle_type handle) { @@ -541,21 +538,15 @@ public: * */ void erase(handle_type const & handle) { - node_pointer n = handle.node_; - node_pointer parent = n->get_parent(); + node_pointer element = handle.node_; + node_pointer parent = element->get_parent(); if (parent) - parent->children.erase(node_list_type::s_iterator_to(*n)); + parent->children.erase(node_list_type::s_iterator_to(*element)); else - roots.erase(node_list_type::s_iterator_to(*n)); + roots.erase(node_list_type::s_iterator_to(*element)); - add_children_to_root(n); - consolidate(); - - n->~node(); - allocator_type::deallocate(n, 1); - - size_holder::decrement(); + finish_erase_or_pop(element); } /// \copydoc boost::heap::priority_queue::begin @@ -582,7 +573,7 @@ public: } /** - * \b Effects: Returns an ordered iterator to the first element contained in the priority queue. + * \b Effects: Returns an ordered iterator to the end of the priority queue. * * \b Note: Ordered iterators traverse the priority queue in heap order. * */ @@ -607,9 +598,10 @@ public: roots.splice(roots.end(), rhs.roots); + rhs.top_element = NULL; rhs.set_size(0); - super_t::set_stability_count(std::max(super_t::get_stability_count(), + super_t::set_stability_count((std::max)(super_t::get_stability_count(), rhs.get_stability_count())); rhs.set_stability_count(0); } @@ -756,6 +748,20 @@ private: while (it != roots.end()); } + void finish_erase_or_pop(node_pointer erased_node) + { + add_children_to_root(erased_node); + + erased_node->~node(); + allocator_type::deallocate(erased_node, 1); + + size_holder::decrement(); + if (!empty()) + consolidate(); + else + top_element = NULL; + } + mutable node_pointer top_element; node_list_type roots; #endif |