Mercurial > hg > vamp-build-and-test

annotate DEPENDENCIES/generic/include/boost/pending/mutable_heap.hpp @ 133:4acb5d8d80b6 tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Don't fail environmental check if README.md exists (but .txt and no-suffix don't)
author Chris Cannam
date Tue, 30 Jul 2019 12:25:44 +0100
parents 2665513ce2d3
children
rev   line source
Chris@16 1 //
Chris@16 2 //=======================================================================
Chris@16 3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16 4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16 5 //
Chris@16 6 // Distributed under the Boost Software License, Version 1.0. (See
Chris@16 7 // accompanying file LICENSE_1_0.txt or copy at
Chris@16 8 // http://www.boost.org/LICENSE_1_0.txt)
Chris@16 9 //=======================================================================
Chris@16 10 //
Chris@16 11 #ifndef BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
Chris@16 12 #define BOOST_GRAPH_DETAIL_MUTABLE_HEAP_H
Chris@16 13
Chris@16 14 /*
Chris@16 15 There are a few things wrong with this set of functions.
Chris@16 16
Chris@16 17 ExternalData should be removed, it is not part of the core
Chris@16 18 algorithm. It can be handled inside the tree nodes.
Chris@16 19
Chris@16 20 The swap() should be replaced by assignment since its use is causing
Chris@16 21 the number of memory references to double.
Chris@16 22
Chris@16 23 The min_element should be replaced by a fixed length loop
Chris@16 24 (fixed at d for d-heaps).
Chris@16 25
Chris@16 26 The member functions of TreeNode should be changed to global
Chris@16 27 functions.
Chris@16 28
Chris@16 29 These functions will be replaced by those in heap_tree.h
Chris@16 30
Chris@16 31 */
Chris@16 32
Chris@16 33 namespace boost {
Chris@16 34
Chris@16 35 template <class TreeNode, class Compare, class ExternalData>
Chris@16 36 inline TreeNode up_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
Chris@16 37 while (x.has_parent() && comp(x, x.parent()))
Chris@16 38 x.swap(x.parent(), edata);
Chris@16 39 return x;
Chris@16 40 }
Chris@16 41
Chris@16 42 template <class TreeNode, class Compare, class ExternalData>
Chris@16 43 inline TreeNode down_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
Chris@16 44 while (x.children().size() > 0) {
Chris@16 45 typename TreeNode::children_type::iterator
Chris@16 46 child_iter = std::min_element(x.children().begin(),
Chris@16 47 x.children().end(),
Chris@16 48 comp);
Chris@16 49 if (comp(*child_iter, x))
Chris@16 50 x.swap(*child_iter, edata);
Chris@16 51 else
Chris@16 52 break;
Chris@16 53 }
Chris@16 54 return x;
Chris@16 55 }
Chris@16 56
Chris@16 57 template <class TreeNode, class Compare, class ExternalData>
Chris@16 58 inline void update_heap(TreeNode x, const Compare& comp, ExternalData& edata) {
Chris@16 59 x = down_heap(x, comp, edata);
Chris@16 60 (void)up_heap(x, comp, edata);
Chris@16 61 }
Chris@16 62
Chris@16 63 }
Chris@16 64 #endif