]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2005-2019 Free Software Foundation, Inc. |
4569a895 AT |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License | |
748086b7 JJ |
17 | // along with this library; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. | |
4569a895 | 19 | |
4569a895 AT |
20 | |
21 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
22 | ||
23 | // Permission to use, copy, modify, sell, and distribute this software | |
24 | // is hereby granted without fee, provided that the above copyright | |
25 | // notice appears in all copies, and that both that copyright notice | |
26 | // and this permission notice appear in supporting documentation. None | |
27 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
28 | // representation about the suitability of this software for any | |
29 | // purpose. It is provided "as is" without express or implied | |
30 | // warranty. | |
31 | ||
32 | /** | |
33 | * @file priority_queue_xref_example.cpp | |
34 | * A basic example showing how to cross-reference priority queues and other | |
35 | * containers for erase. | |
36 | */ | |
37 | ||
38 | /** | |
39 | * This example shows how to cross-reference priority queues | |
40 | * and other containers. I.e., using an associative container to | |
41 | * map keys to entries in a priority queue, and using the priority | |
42 | * queue to map entries to the associative container. The combination | |
43 | * can be used for fast operations involving both priorities and | |
44 | * arbitrary keys. | |
45 | * | |
46 | * The most useful examples of this technique are usually from the | |
47 | * field of graph algorithms (where erasing or modifying an arbitrary | |
48 | * entry of a priority queue is sometimes necessary), but a full-blown | |
49 | * example would be too long. Instead, this example shows a very simple | |
50 | * version of Dijkstra's | |
51 | */ | |
52 | ||
53 | #include <iostream> | |
54 | #include <cassert> | |
55 | #include <ext/pb_ds/priority_queue.hpp> | |
56 | #include <ext/pb_ds/assoc_container.hpp> | |
57 | ||
58 | using namespace std; | |
5e11f978 | 59 | using namespace __gnu_pbds; |
4569a895 AT |
60 | |
61 | // A priority queue of integers, which supports fast pushes, | |
62 | // duplicated-int avoidance, and arbitrary-int erases. | |
63 | class mapped_priority_queue | |
64 | { | |
65 | public: | |
66 | ||
67 | // Pushes an int into the container. If the key is already in, this | |
68 | // is a no-op. | |
69 | void | |
70 | push(const int& r_str); | |
71 | ||
72 | // Returns a const reference to the largest int in the container. | |
7919bb2f | 73 | int |
4569a895 AT |
74 | top() const |
75 | { | |
76 | assert(!empty()); | |
77 | return m_pq.top(); | |
78 | } | |
79 | ||
80 | // Erases the largest int in the container. | |
81 | void | |
82 | pop(); | |
83 | ||
84 | // Erases an arbitrary int. If the int is not in the container, this | |
85 | // is a no-op, and the return value is false. | |
86 | bool | |
87 | erase(const int& r_str); | |
88 | ||
89 | bool | |
90 | empty() const | |
91 | { return m_pq.empty(); } | |
92 | ||
93 | size_t | |
94 | size() const | |
95 | { return m_pq.size(); } | |
96 | ||
97 | private: | |
98 | // A priority queue of strings. | |
5e11f978 | 99 | typedef __gnu_pbds::priority_queue< int> pq_t; |
4569a895 AT |
100 | |
101 | // A hash-table mapping strings to point_iterators inside the | |
102 | // priority queue. | |
103 | typedef cc_hash_table< int, pq_t::point_iterator> map_t; | |
104 | ||
105 | pq_t m_pq; | |
106 | map_t m_map; | |
107 | }; | |
108 | ||
109 | void | |
110 | mapped_priority_queue:: | |
111 | push(const int& r_str) | |
112 | { | |
113 | // First check if the int is already in the container. If so, just return. | |
114 | if (m_map.find(r_str) != m_map.end()) | |
115 | return; | |
116 | ||
117 | // Push the int into the priority queue, and store a point_iterator to it. | |
118 | pq_t::point_iterator pq_it = m_pq.push(r_str); | |
119 | ||
120 | try | |
121 | { | |
122 | // Now make the map associate the int to the point_iterator. | |
123 | m_map[r_str] = pq_it; | |
124 | } | |
125 | catch(...) | |
126 | { | |
127 | // If the above failed, we need to remove the int from the | |
128 | // priority queue as well. | |
129 | m_pq.erase(pq_it); | |
130 | throw; | |
131 | } | |
132 | } | |
133 | ||
134 | void | |
135 | mapped_priority_queue:: | |
136 | pop() | |
137 | { | |
138 | assert(!empty()); | |
139 | ||
140 | // Erase the int from the map. | |
141 | m_map.erase(m_pq.top()); | |
142 | ||
143 | // ...then from the priority queue. | |
144 | m_pq.pop(); | |
145 | } | |
146 | ||
147 | bool | |
148 | mapped_priority_queue:: | |
149 | erase(const int& r_str) | |
150 | { | |
151 | map_t::point_iterator map_it = m_map.find(r_str); | |
152 | ||
153 | // If the int is not in the map, this is a no-op. | |
154 | if (map_it == m_map.end()) | |
155 | return false; | |
156 | ||
157 | // Otherwise, we erase it from the priority queue. | |
158 | m_pq.erase(map_it->second); | |
159 | ||
160 | // ...then from the map. | |
161 | m_map.erase(r_str); | |
162 | ||
163 | return true; | |
164 | } | |
165 | ||
166 | int main() | |
167 | { | |
168 | // Push some values into the container object. | |
169 | mapped_priority_queue m; | |
170 | m.push(1); | |
171 | m.push(2); | |
172 | ||
173 | // The following four operations are no-ops: 2 and 1 are already in | |
174 | // the container. | |
175 | m.push(2); | |
176 | m.push(2); | |
177 | m.push(2); | |
178 | m.push(1); | |
179 | ||
180 | m.push(10); | |
181 | m.push(11); | |
182 | m.push(12); | |
183 | ||
184 | // The size should be 5, since m contains the set {1, 2, 10, 11, 12}. | |
185 | assert(m.size() == 5); | |
186 | ||
187 | // The largest value should be 12. | |
188 | assert(m.top() == 12); | |
189 | ||
190 | // Now erase some values. | |
191 | ||
192 | // Erasing 1 actually erases a value. | |
193 | assert(m.erase(1)); | |
194 | ||
195 | // ...but erasing 1 again is a no-op. | |
196 | assert(!m.erase(1)); | |
197 | ||
198 | // The size should be 5, since m contains the set {2, 10, 11, 12}. | |
199 | assert(m.size() == 4); | |
200 | ||
201 | // Now print the values in the container. | |
202 | while (!m.empty()) | |
203 | { | |
204 | cout << m.top() << endl; | |
205 | m.pop(); | |
206 | } | |
207 | ||
208 | return 0; | |
209 | } | |
210 |