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