epoc32/include/stdapis/boost/pending/mutable_heap.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     1 //
     2 //=======================================================================
     3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     5 //
     6 // Distributed under the Boost Software License, Version 1.0. (See
     7 // accompanying file LICENSE_1_0.txt or copy at
     8 // http://www.boost.org/LICENSE_1_0.txt)
     9 //=======================================================================
    10 //
    11 #ifndef BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
    12 #define BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
    13 
    14 /*
    15   There are a few things wrong with this set of functions.
    16 
    17   ExternalData should be removed, it is not part of the core
    18   algorithm. It can be handled inside the tree nodes.
    19 
    20   The swap() should be replaced by assignment since its use is causing
    21   the number of memory references to double.
    22 
    23   The min_element should be replaced by a fixed length loop
    24   (fixed at d for d-heaps).
    25 
    26   The member functions of TreeNode should be changed to global
    27   functions.
    28 
    29   These functions will be replaced by those in heap_tree.h
    30 
    31  */
    32 
    33 namespace boost {
    34 
    35   template <class TreeNode, class Compare, class ExternalData>
    36   inline TreeNode up_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
    37     while (x.has_parent() && comp(x, x.parent()))
    38       x.swap(x.parent(), edata);
    39     return x;
    40   }
    41 
    42   template <class TreeNode, class Compare, class ExternalData>
    43   inline TreeNode down_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
    44     while (x.children().size() > 0) {
    45       typename TreeNode::children_type::iterator 
    46         child_iter = std::min_element(x.children().begin(),
    47                                       x.children().end(), 
    48                                       comp);
    49       if (comp(*child_iter, x))
    50         x.swap(*child_iter, edata);
    51       else
    52         break;
    53     }
    54     return x;
    55   }
    56 
    57   template <class TreeNode, class Compare, class ExternalData>
    58   inline void update_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
    59     x = down_heap(x, comp, edata);
    60     (void)up_heap(x, comp, edata);
    61   }
    62 
    63 }
    64 #endif