1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/pending/mutable_heap.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,64 @@
     1.4 +//
     1.5 +//=======================================================================
     1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.8 +//
     1.9 +// Distributed under the Boost Software License, Version 1.0. (See
    1.10 +// accompanying file LICENSE_1_0.txt or copy at
    1.11 +// http://www.boost.org/LICENSE_1_0.txt)
    1.12 +//=======================================================================
    1.13 +//
    1.14 +#ifndef BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
    1.15 +#define BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
    1.16 +
    1.17 +/*
    1.18 +  There are a few things wrong with this set of functions.
    1.19 +
    1.20 +  ExternalData should be removed, it is not part of the core
    1.21 +  algorithm. It can be handled inside the tree nodes.
    1.22 +
    1.23 +  The swap() should be replaced by assignment since its use is causing
    1.24 +  the number of memory references to double.
    1.25 +
    1.26 +  The min_element should be replaced by a fixed length loop
    1.27 +  (fixed at d for d-heaps).
    1.28 +
    1.29 +  The member functions of TreeNode should be changed to global
    1.30 +  functions.
    1.31 +
    1.32 +  These functions will be replaced by those in heap_tree.h
    1.33 +
    1.34 + */
    1.35 +
    1.36 +namespace boost {
    1.37 +
    1.38 +  template <class TreeNode, class Compare, class ExternalData>
    1.39 +  inline TreeNode up_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
    1.40 +    while (x.has_parent() && comp(x, x.parent()))
    1.41 +      x.swap(x.parent(), edata);
    1.42 +    return x;
    1.43 +  }
    1.44 +
    1.45 +  template <class TreeNode, class Compare, class ExternalData>
    1.46 +  inline TreeNode down_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
    1.47 +    while (x.children().size() > 0) {
    1.48 +      typename TreeNode::children_type::iterator 
    1.49 +        child_iter = std::min_element(x.children().begin(),
    1.50 +                                      x.children().end(), 
    1.51 +                                      comp);
    1.52 +      if (comp(*child_iter, x))
    1.53 +        x.swap(*child_iter, edata);
    1.54 +      else
    1.55 +        break;
    1.56 +    }
    1.57 +    return x;
    1.58 +  }
    1.59 +
    1.60 +  template <class TreeNode, class Compare, class ExternalData>
    1.61 +  inline void update_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
    1.62 +    x = down_heap(x, comp, edata);
    1.63 +    (void)up_heap(x, comp, edata);
    1.64 +  }
    1.65 +
    1.66 +}
    1.67 +#endif