]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
405feeb8 | 3 | // Copyright (C) 2005-2013 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/>. | |
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 native_priority_queue.hpp | |
34 | * Contains an adapter to Dinkumware/SGI tree tables | |
35 | */ | |
36 | ||
37 | #ifndef PB_DS_NATIVE_PRIORITY_QUEUE_HPP | |
38 | #define PB_DS_NATIVE_PRIORITY_QUEUE_HPP | |
39 | ||
4569a895 AT |
40 | #include <string> |
41 | #include <vector> | |
42 | #include <queue> | |
43 | #include <deque> | |
382a1351 BK |
44 | #include <ext/pb_ds/detail/standard_policies.hpp> |
45 | #include <ext/pb_ds/detail/type_utils.hpp> | |
46 | #include <io/xml.hpp> | |
4569a895 | 47 | |
5e11f978 | 48 | namespace __gnu_pbds |
4569a895 | 49 | { |
4569a895 AT |
50 | namespace test |
51 | { | |
4569a895 AT |
52 | namespace detail |
53 | { | |
a345e45d | 54 | template<typename Value_Type, bool Vector, typename _Alloc> |
4569a895 AT |
55 | struct base_seq |
56 | { | |
382a1351 | 57 | private: |
a345e45d | 58 | typedef typename _Alloc::template rebind<Value_Type> value_rebind; |
382a1351 BK |
59 | |
60 | public: | |
61 | typedef std::vector<Value_Type, typename value_rebind::other> type; | |
4569a895 AT |
62 | }; |
63 | ||
a345e45d BK |
64 | template<typename Value_Type, typename _Alloc> |
65 | struct base_seq<Value_Type, false, _Alloc> | |
4569a895 | 66 | { |
382a1351 | 67 | private: |
a345e45d | 68 | typedef typename _Alloc::template rebind<Value_Type> value_rebind; |
4569a895 | 69 | |
382a1351 BK |
70 | public: |
71 | typedef std::deque<Value_Type, typename value_rebind::other> type; | |
72 | }; | |
4569a895 AT |
73 | } // namespace detail |
74 | ||
382a1351 BK |
75 | struct native_pq_tag |
76 | { }; | |
77 | ||
78 | #define PB_DS_CLASS_C_DEC \ | |
a345e45d | 79 | native_priority_queue<Value_Type, Vector, Cmp_Fn, _Alloc> |
4569a895 | 80 | |
382a1351 | 81 | #define PB_DS_BASE_C_DEC \ |
a345e45d | 82 | std::priority_queue<Value_Type, typename detail::base_seq<Value_Type, Vector, _Alloc>::type, Cmp_Fn> |
4569a895 AT |
83 | |
84 | template<typename Value_Type, | |
85 | bool Vector, | |
382a1351 | 86 | typename Cmp_Fn = std::less<Value_Type>, |
a345e45d | 87 | typename _Alloc = std::allocator<char> > |
4569a895 AT |
88 | class native_priority_queue : public PB_DS_BASE_C_DEC |
89 | { | |
90 | private: | |
91 | typedef PB_DS_BASE_C_DEC base_type; | |
a345e45d | 92 | typedef typename _Alloc::template rebind<Value_Type> value_rebind; |
4569a895 AT |
93 | |
94 | public: | |
95 | typedef Value_Type value_type; | |
382a1351 | 96 | typedef typename value_rebind::other::const_reference const_reference; |
4569a895 | 97 | typedef native_pq_tag container_category; |
4569a895 AT |
98 | typedef Cmp_Fn cmp_fn; |
99 | ||
4569a895 AT |
100 | native_priority_queue() : base_type() |
101 | { } | |
102 | ||
103 | template<typename It> | |
104 | native_priority_queue(It f, It l) : base_type(f, l) | |
105 | { } | |
106 | ||
107 | static std::string | |
108 | name() | |
109 | { | |
110 | if (Vector) | |
111 | return ("n_pq_vector"); | |
4569a895 AT |
112 | return ("n_pq_deque"); |
113 | } | |
114 | ||
115 | static std::string | |
116 | desc() | |
117 | { | |
118 | if (Vector) | |
382a1351 BK |
119 | return make_xml_tag("type", "value", "std::priority_queue_vector"); |
120 | return make_xml_tag("type", "value", "std::priority_queue_deque"); | |
4569a895 AT |
121 | } |
122 | ||
123 | void | |
124 | clear() | |
382a1351 | 125 | { *static_cast<base_type*>(this) = base_type(); } |
4569a895 AT |
126 | |
127 | void | |
128 | erase(const_reference r_val) | |
129 | { | |
130 | base_type tmp; | |
4569a895 AT |
131 | Cmp_Fn cmp; |
132 | ||
133 | while (cmp(base_type::top(), r_val) || cmp(r_val, base_type::top())) | |
134 | { | |
135 | tmp.push(base_type::top()); | |
4569a895 AT |
136 | base_type::pop(); |
137 | } | |
138 | ||
139 | if (!base_type::empty()) | |
140 | { | |
141 | base_type::pop(); | |
4569a895 AT |
142 | while (!base_type::empty()) |
143 | { | |
144 | tmp.push(base_type::top()); | |
4569a895 AT |
145 | base_type::pop(); |
146 | } | |
147 | } | |
382a1351 | 148 | *static_cast<base_type* >(this) = tmp; |
4569a895 AT |
149 | } |
150 | ||
151 | template<typename Pred> | |
152 | size_t | |
153 | erase_if(Pred pred) | |
154 | { | |
155 | base_type tmp; | |
4569a895 | 156 | std::size_t ersd = 0; |
4569a895 AT |
157 | while (!base_type::empty()) |
158 | { | |
159 | if (!pred(base_type::top())) | |
160 | tmp.push(base_type::top()); | |
161 | else | |
162 | ++ersd; | |
4569a895 AT |
163 | base_type::pop(); |
164 | } | |
165 | ||
382a1351 | 166 | *static_cast<base_type*>(this) = tmp; |
4569a895 AT |
167 | return ersd; |
168 | } | |
169 | ||
170 | template<typename Pred> | |
171 | void | |
172 | split(Pred pred, PB_DS_CLASS_C_DEC& other) | |
173 | { | |
174 | base_type tmp; | |
4569a895 | 175 | other.clear(); |
4569a895 AT |
176 | while (!base_type::empty()) |
177 | { | |
178 | if (!pred(base_type::top())) | |
179 | tmp.push(base_type::top()); | |
180 | else | |
181 | other.push(base_type::top()); | |
4569a895 AT |
182 | base_type::pop(); |
183 | } | |
382a1351 | 184 | *static_cast<base_type*>(this) = tmp; |
4569a895 AT |
185 | } |
186 | ||
187 | void | |
188 | modify(const_reference r_old, const_reference r_new) | |
189 | { | |
190 | erase(r_old); | |
94df301f | 191 | this->push(r_new); |
4569a895 AT |
192 | } |
193 | ||
194 | void | |
195 | join(PB_DS_CLASS_C_DEC& other) | |
196 | { | |
197 | std::vector<value_type> a_tmp; | |
4569a895 AT |
198 | while (!base_type::empty()) |
199 | { | |
200 | a_tmp.push_back(base_type::top()); | |
4569a895 AT |
201 | base_type::pop(); |
202 | } | |
203 | ||
204 | while (!other.empty()) | |
205 | { | |
206 | a_tmp.push_back(other.top()); | |
4569a895 AT |
207 | other.pop(); |
208 | } | |
209 | ||
382a1351 | 210 | *static_cast<base_type*>(this) = base_type(a_tmp.begin(), a_tmp.end()); |
4569a895 AT |
211 | } |
212 | ||
213 | Cmp_Fn | |
214 | get_cmp_fn() const | |
382a1351 | 215 | { return Cmp_Fn(); } |
4569a895 AT |
216 | }; |
217 | ||
218 | #undef PB_DS_BASE_C_DEC | |
4569a895 AT |
219 | #undef PB_DS_CLASS_C_DEC |
220 | ||
221 | } // namespace test | |
5e11f978 | 222 | } // namespace __gnu_pbds |
4569a895 | 223 | |
382a1351 | 224 | #endif |