/usr/include/boost/pending/mutable_queue.hpp is in libboost1.54-dev 1.54.0-4ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | //
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//
#ifndef BOOST_MUTABLE_QUEUE_HPP
#define BOOST_MUTABLE_QUEUE_HPP
#include <vector>
#include <algorithm>
#include <functional>
#include <boost/property_map/property_map.hpp>
#include <boost/pending/mutable_heap.hpp>
#include <boost/pending/is_heap.hpp>
#include <boost/graph/detail/array_binary_tree.hpp>
#include <iterator>
namespace boost {
// The mutable queue whose elements are indexed
//
// This adaptor provides a special kind of priority queue that has
// and update operation. This allows the ordering of the items to
// change. After the ordering criteria for item x changes, one must
// call the Q.update(x)
//
// In order to efficiently find x in the queue, a functor must be
// provided to map value_type to a unique ID, which the
// mutable_queue will then use to map to the location of the
// item. The ID's generated must be between 0 and N, where N is the
// value passed to the constructor of mutable_queue
template <class IndexedType,
class RandomAccessContainer = std::vector<IndexedType>,
class Comp = std::less<typename RandomAccessContainer::value_type>,
class ID = identity_property_map >
class mutable_queue {
public:
typedef IndexedType value_type;
typedef typename RandomAccessContainer::size_type size_type;
protected:
typedef typename RandomAccessContainer::iterator iterator;
#if !defined BOOST_NO_STD_ITERATOR_TRAITS
typedef array_binary_tree_node<iterator, ID> Node;
#else
typedef array_binary_tree_node<iterator, value_type, ID> Node;
#endif
typedef compare_array_node<RandomAccessContainer,Comp> Compare;
typedef std::vector<size_type> IndexArray;
public:
typedef Compare value_compare;
typedef ID id_generator;
mutable_queue(size_type n, const Comp& x, const ID& _id)
: index_array(n), comp(x), id(_id) {
c.reserve(n);
}
template <class ForwardIterator>
mutable_queue(ForwardIterator first, ForwardIterator last,
const Comp& x, const ID& _id)
: index_array(std::distance(first, last)), comp(x), id(_id)
{
while( first != last ) {
push(*first);
++first;
}
}
bool empty() const { return c.empty(); }
void pop() {
value_type tmp = c.back();
c.back() = c.front();
c.front() = tmp;
size_type id_f = get(id, c.back());
size_type id_b = get(id, tmp);
size_type i = index_array[ id_b ];
index_array[ id_b ] = index_array[ id_f ];
index_array[ id_f ] = i;
c.pop_back();
Node node(c.begin(), c.end(), c.begin(), id);
down_heap(node, comp, index_array);
}
void push(const IndexedType& x) {
c.push_back(x);
/*set index-array*/
index_array[ get(id, x) ] = c.size()-1;
Node node(c.begin(), c.end(), c.end() - 1, id);
up_heap(node, comp, index_array);
}
void update(const IndexedType& x) {
size_type current_pos = index_array[ get(id, x) ];
c[current_pos] = x;
Node node(c.begin(), c.end(), c.begin()+current_pos, id);
update_heap(node, comp, index_array);
}
value_type& front() { return c.front(); }
value_type& top() { return c.front(); }
const value_type& front() const { return c.front(); }
const value_type& top() const { return c.front(); }
size_type size() const { return c.size(); }
void clear() { c.clear(); }
#if 0
// dwa 2003/7/11 - I don't know what compiler is supposed to
// be able to compile this, but is_heap is not standard!!
bool test() {
return std::is_heap(c.begin(), c.end(), Comp());
}
#endif
protected:
IndexArray index_array;
Compare comp;
RandomAccessContainer c;
ID id;
};
}
#endif // BOOST_MUTABLE_QUEUE_HPP
|