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