boost/pending/mutable_heap.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
0012 #define BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
0013
0014 /*
0015   There are a few things wrong with this set of functions.
0016
0017   ExternalData should be removed, it is not part of the core
0018   algorithm. It can be handled inside the tree nodes.
0019
0020   The swap() should be replaced by assignment since its use is causing
0021   the number of memory references to double.
0022
0023   The min_element should be replaced by a fixed length loop
0024   (fixed at d for d-heaps).
0025
0026   The member functions of TreeNode should be changed to global
0027   functions.
0028
0029   These functions will be replaced by those in heap_tree.h
0030
0031  */
0032
0033 namespace boost
0034 {
0035
0036 template < class TreeNode, class Compare, class ExternalData >
0037 inline TreeNode up_heap(TreeNode x, const Compare& comp, ExternalData& edata)
0038 {
0039     while (x.has_parent() && comp(x, x.parent()))
0040         x.swap(x.parent(), edata);
0041     return x;
0042 }
0043
0044 template < class TreeNode, class Compare, class ExternalData >
0045 inline TreeNode down_heap(TreeNode x, const Compare& comp, ExternalData& edata)
0046 {
0047     while (x.children().size() > 0)
0048     {
0049         typename TreeNode::children_type::iterator child_iter
0050             = std::min_element(x.children().begin(), x.children().end(), comp);
0051         if (comp(*child_iter, x))
0052             x.swap(*child_iter, edata);
0053         else
0054             break;
0055     }
0056     return x;
0057 }
0058
0059 template < class TreeNode, class Compare, class ExternalData >
0060 inline void update_heap(TreeNode x, const Compare& comp, ExternalData& edata)
0061 {
0062     x = down_heap(x, comp, edata);
0063     (void)up_heap(x, comp, edata);
0064 }
0065
0066 }
0067 #endif