]>
Commit | Line | Data |
---|---|---|
fd1e1726 BK |
1 | // -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2005 Free Software Foundation, Inc. | |
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 | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
83f51799 | 18 | // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, |
fd1e1726 BK |
19 | // USA. |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
30 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
31 | ||
32 | // Permission to use, copy, modify, sell, and distribute this software | |
33 | // is hereby granted without fee, provided that the above copyright | |
34 | // notice appears in all copies, and that both that copyright notice and | |
35 | // this permission notice appear in supporting documentation. None of | |
36 | // the above authors, nor IBM Haifa Research Laboratories, make any | |
37 | // representation about the suitability of this software for any | |
38 | // purpose. It is provided "as is" without express or implied warranty. | |
39 | ||
40 | /* | |
41 | * @file order_statistics_imp.hpp | |
42 | * Contains forward declarations for order_statistics_key | |
43 | */ | |
44 | ||
45 | #ifndef ORDER_STATISTICS_IMP_HPP | |
46 | #define ORDER_STATISTICS_IMP_HPP | |
47 | ||
48 | #define PB_ASSOC_CLASS_T_DEC \ | |
49 | template<class Key, class Allocator> | |
50 | ||
51 | #define PB_ASSOC_CLASS_C_DEC \ | |
52 | order_statistics_key< \ | |
53 | Key, \ | |
54 | Allocator> | |
55 | ||
56 | PB_ASSOC_CLASS_T_DEC | |
57 | inline | |
58 | PB_ASSOC_CLASS_C_DEC:: | |
59 | order_statistics_key(const_key_reference r_key) : | |
60 | m_key(r_key), | |
61 | m_rank(1) | |
62 | { } | |
63 | ||
64 | PB_ASSOC_CLASS_T_DEC | |
65 | inline | |
66 | PB_ASSOC_CLASS_C_DEC:: | |
67 | operator typename PB_ASSOC_CLASS_C_DEC::key_reference() | |
68 | { | |
69 | return (m_key); | |
70 | } | |
71 | ||
72 | PB_ASSOC_CLASS_T_DEC | |
73 | inline | |
74 | PB_ASSOC_CLASS_C_DEC:: | |
75 | operator typename PB_ASSOC_CLASS_C_DEC::key_type() const | |
76 | { | |
77 | return (m_key); | |
78 | } | |
79 | ||
80 | #undef PB_ASSOC_CLASS_T_DEC | |
81 | ||
82 | #undef PB_ASSOC_CLASS_C_DEC | |
83 | ||
84 | #define PB_ASSOC_CLASS_T_DEC \ | |
85 | template<class Cmp_Fn, class Allocator> | |
86 | ||
87 | #define PB_ASSOC_CLASS_C_DEC \ | |
88 | order_statistics_key_cmp< \ | |
89 | Cmp_Fn, \ | |
90 | Allocator> | |
91 | ||
92 | PB_ASSOC_CLASS_T_DEC | |
93 | inline | |
94 | PB_ASSOC_CLASS_C_DEC:: | |
95 | order_statistics_key_cmp() | |
96 | { } | |
97 | ||
98 | PB_ASSOC_CLASS_T_DEC | |
99 | inline | |
100 | PB_ASSOC_CLASS_C_DEC:: | |
101 | order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn) : | |
102 | Cmp_Fn(r_cmp_fn) | |
103 | { } | |
104 | ||
105 | PB_ASSOC_CLASS_T_DEC | |
106 | inline bool | |
107 | PB_ASSOC_CLASS_C_DEC:: | |
108 | operator()(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const | |
109 | { | |
110 | return Cmp_Fn::operator()((key_type)r_lhs_key, (key_type)r_rhs_key); | |
111 | } | |
112 | ||
113 | PB_ASSOC_CLASS_T_DEC | |
114 | inline typename PB_ASSOC_CLASS_C_DEC::cmp_fn& | |
115 | PB_ASSOC_CLASS_C_DEC:: | |
116 | get_cmp_fn() | |
117 | { | |
118 | return (*this); | |
119 | } | |
120 | ||
121 | PB_ASSOC_CLASS_T_DEC | |
122 | inline const typename PB_ASSOC_CLASS_C_DEC::cmp_fn& | |
123 | PB_ASSOC_CLASS_C_DEC:: | |
124 | get_cmp_fn() const | |
125 | { | |
126 | return (*this); | |
127 | } | |
128 | ||
129 | #undef PB_ASSOC_CLASS_T_DEC | |
130 | ||
131 | #undef PB_ASSOC_CLASS_C_DEC | |
132 | ||
133 | #define PB_ASSOC_CLASS_T_DEC \ | |
134 | template<class Key, class Allocator> | |
135 | ||
136 | #define PB_ASSOC_CLASS_C_DEC \ | |
137 | order_statistics_node_updator< \ | |
138 | Key, \ | |
139 | Allocator> | |
140 | ||
141 | PB_ASSOC_CLASS_T_DEC | |
142 | inline void | |
143 | PB_ASSOC_CLASS_C_DEC:: | |
144 | operator()(const_key_pointer p_key, const_key_pointer p_l_child_key, const_key_pointer p_r_child_key) | |
145 | { | |
146 | /* | |
147 | * The left rank is 0 if there is no left child, | |
148 | * or the rank of the left child, otherwise. | |
149 | */ | |
150 | const size_type l_rank =(p_l_child_key == NULL)? 0 : p_l_child_key->m_rank; | |
151 | ||
152 | /* | |
153 | * The right rank is 0 if there is no right child, | |
154 | * or the rank of the right child, otherwise. | |
155 | */ | |
156 | const size_type r_rank =(p_r_child_key == NULL)? 0 : p_r_child_key->m_rank; | |
157 | ||
158 | /* | |
159 | * The rand of the entry is the sumb of the ranks of its | |
160 | * children + 1 (for itself). | |
161 | */ | |
162 | p_key->m_rank = 1 + l_rank + r_rank; | |
163 | } | |
164 | ||
165 | PB_ASSOC_CLASS_T_DEC | |
166 | inline void | |
167 | PB_ASSOC_CLASS_C_DEC:: | |
168 | swap(PB_ASSOC_CLASS_C_DEC& /*r_other*/) | |
169 | { } | |
170 | ||
171 | #undef PB_ASSOC_CLASS_T_DEC | |
172 | ||
173 | #undef PB_ASSOC_CLASS_C_DEC | |
174 | ||
175 | #define PB_ASSOC_CLASS_T_DEC \ | |
176 | template<class Cntnr> | |
177 | ||
178 | #define PB_ASSOC_CLASS_C_DEC \ | |
179 | find_by_order< \ | |
180 | Cntnr> | |
181 | ||
182 | PB_ASSOC_CLASS_T_DEC | |
183 | inline typename PB_ASSOC_CLASS_C_DEC::iterator | |
184 | PB_ASSOC_CLASS_C_DEC:: | |
185 | operator()(Cntnr& r_c, size_type order) const | |
186 | { | |
187 | return find(r_c, order); | |
188 | } | |
189 | ||
190 | PB_ASSOC_CLASS_T_DEC | |
191 | inline typename PB_ASSOC_CLASS_C_DEC::const_iterator | |
192 | PB_ASSOC_CLASS_C_DEC:: | |
193 | operator()(const Cntnr& r_c, size_type order) const | |
194 | { | |
195 | return find(r_c, order); | |
196 | } | |
197 | ||
198 | PB_ASSOC_CLASS_T_DEC | |
199 | inline typename PB_ASSOC_CLASS_C_DEC::const_iterator | |
200 | PB_ASSOC_CLASS_C_DEC:: | |
201 | find(const Cntnr& r_c, size_type order) | |
202 | { | |
203 | if (order > r_c.size()) | |
204 | return (r_c.end()); | |
205 | ||
206 | /* | |
207 | * Start at the top of the tree. | |
208 | */ | |
209 | typename Cntnr::const_node_iterator it = r_c.node_begin(); | |
210 | ||
211 | /* | |
212 | * Loop up to a leaf. | |
213 | */ | |
214 | while (it != r_c.node_end()) | |
215 | { | |
216 | typename Cntnr::const_node_iterator l_it = it.l_child(); | |
217 | ||
218 | /* | |
219 | * The order of the element, o, is the rank of the left | |
220 | * child (for the entry itself). | |
221 | */ | |
222 | const size_type o = (l_it == r_c.node_end())? | |
223 | 0 :(*l_it)->m_rank; | |
224 | ||
225 | /* | |
226 | * If the current order, o, is the order requested, | |
227 | * the key has been found. | |
228 | */ | |
229 | if (order == o) | |
230 | return (*it); | |
231 | /* | |
232 | * If the current order, o, is larger than the order requested, | |
233 | * we should move to the left subtree. | |
234 | */ | |
235 | else if (order < o) | |
236 | it = l_it; | |
237 | /* | |
238 | * Otherwise adujst the requested order and move to the right subtree. | |
239 | */ | |
240 | else | |
241 | { | |
242 | order -= o + 1; | |
243 | ||
244 | it = it.r_child(); | |
245 | } | |
246 | } | |
247 | ||
248 | return (r_c.end()); | |
249 | } | |
250 | ||
251 | PB_ASSOC_CLASS_T_DEC | |
252 | inline typename PB_ASSOC_CLASS_C_DEC::iterator | |
253 | PB_ASSOC_CLASS_C_DEC:: | |
254 | find(Cntnr& r_c, size_type order) | |
255 | { | |
256 | if (order > r_c.size()) | |
257 | return (r_c.end()); | |
258 | ||
259 | /* | |
260 | * Start at the top of the tree. | |
261 | */ | |
262 | typename Cntnr::node_iterator it = r_c.node_begin(); | |
263 | ||
264 | /* | |
265 | * Loop up to a leaf. | |
266 | */ | |
267 | while (it != r_c.node_end()) | |
268 | { | |
269 | typename Cntnr::node_iterator l_it = it.l_child(); | |
270 | ||
271 | /* | |
272 | * The order of the element, o, is the rank of the left | |
273 | * child (for the entry itself). | |
274 | */ | |
275 | const size_type o = (l_it == r_c.node_end())? | |
276 | 0 : | |
277 | r_c.extract_key(*(*l_it)).m_rank; | |
278 | ||
279 | /* | |
280 | * If the current order, o, is the order requested, | |
281 | * the key has been found. | |
282 | */ | |
283 | if (order == o) | |
284 | return (*it); | |
285 | /* | |
286 | * If the current order, o, is larger than the order requested, | |
287 | * we should move to the left subtree. | |
288 | */ | |
289 | else if (order < o) | |
290 | it = l_it; | |
291 | /* | |
292 | * Otherwise adujst the requested order and move to the right subtree. | |
293 | */ | |
294 | else | |
295 | { | |
296 | order -= o + 1; | |
297 | ||
298 | it = it.r_child(); | |
299 | } | |
300 | } | |
301 | ||
302 | return (r_c.end()); | |
303 | } | |
304 | ||
305 | #undef PB_ASSOC_CLASS_T_DEC | |
306 | ||
307 | #undef PB_ASSOC_CLASS_C_DEC | |
308 | ||
309 | #define PB_ASSOC_CLASS_T_DEC \ | |
310 | template<class Cntnr> | |
311 | ||
312 | #define PB_ASSOC_CLASS_C_DEC \ | |
313 | order_by_key< \ | |
314 | Cntnr> | |
315 | ||
316 | PB_ASSOC_CLASS_T_DEC | |
317 | inline typename PB_ASSOC_CLASS_C_DEC::size_type | |
318 | PB_ASSOC_CLASS_C_DEC:: | |
319 | operator()(const Cntnr& r_c, const underlying_key_type& r_key) const | |
320 | { | |
321 | /* | |
322 | * The logic here is similar to that in order_by_key. | |
323 | */ | |
324 | ||
325 | typename Cntnr::const_node_iterator it = r_c.node_begin(); | |
326 | ||
327 | size_type ord = 0; | |
328 | ||
329 | while (it != r_c.node_end()) | |
330 | { | |
331 | typename Cntnr::const_node_iterator l_it = it.l_child(); | |
332 | ||
333 | if (r_c.get_cmp_fn().get_cmp_fn()( | |
334 | r_key, | |
335 | r_c.extract_key(*(*it)).m_key)) | |
336 | it = l_it; | |
337 | else if (r_c.get_cmp_fn().get_cmp_fn()( | |
338 | r_c.extract_key(*(*it)).m_key, | |
339 | r_key)) | |
340 | { | |
341 | ||
342 | ord += (l_it == r_c.node_end())? | |
343 | 1 : | |
344 | 1 + r_c.extract_key(*(*l_it)).m_rank; | |
345 | ||
346 | it = it.r_child(); | |
347 | } | |
348 | else | |
349 | { | |
350 | ord += (l_it == r_c.node_end())? | |
351 | 0 : | |
352 | r_c.extract_key(*(*l_it)).m_rank; | |
353 | ||
354 | it = r_c.node_end(); | |
355 | } | |
356 | } | |
357 | ||
358 | return (ord); | |
359 | } | |
360 | ||
361 | #undef PB_ASSOC_CLASS_T_DEC | |
362 | ||
363 | #undef PB_ASSOC_CLASS_C_DEC | |
364 | ||
365 | #define PB_ASSOC_CLASS_T_DEC \ | |
366 | template<class Cntnr, class Allocator> | |
367 | ||
368 | #define PB_ASSOC_CLASS_C_DEC \ | |
369 | order_statistics_key_verifier< \ | |
370 | Cntnr, \ | |
371 | Allocator> | |
372 | ||
373 | template<class Cntnr, class Allocator = std::allocator<char> > | |
374 | class order_statistics_key_verifier | |
375 | { | |
376 | public: | |
377 | typedef Cntnr map; | |
378 | ||
379 | typedef Allocator allocator; | |
380 | ||
381 | typedef typename allocator::size_type size_type; | |
382 | ||
383 | typedef | |
384 | typename allocator::template rebind<map>::other::const_reference | |
385 | const_map_reference; | |
386 | ||
387 | public: | |
388 | bool | |
389 | operator()(const Cntnr& r_c) const; | |
390 | ||
391 | private: | |
392 | typedef typename Cntnr::const_node_iterator const_node_iterator; | |
393 | ||
394 | typedef typename Cntnr::const_iterator cntnr_const_it; | |
395 | ||
396 | typedef std::pair<bool, size_type> stat; | |
397 | ||
398 | private: | |
399 | static stat | |
400 | verify_imp(const_node_iterator it, const_node_iterator end_it) | |
401 | { | |
402 | if (it == end_it) | |
403 | return (std::make_pair(true, 0)); | |
404 | ||
405 | const stat l_ret = | |
406 | verify_imp(it.l_child(), end_it); | |
407 | ||
408 | const stat r_ret = | |
409 | verify_imp(it.r_child(), end_it); | |
410 | ||
411 | if (!l_ret.first || !r_ret.first) | |
412 | return (std::make_pair(false, 0)); | |
413 | ||
414 | if ((*it)->m_rank != 1 + l_ret.second + r_ret.second) | |
415 | return (std::make_pair(false, 0)); | |
416 | ||
417 | return (std::make_pair(true, (*it)->m_rank)); | |
418 | } | |
419 | }; | |
420 | ||
421 | PB_ASSOC_CLASS_T_DEC | |
422 | bool | |
423 | PB_ASSOC_CLASS_C_DEC:: | |
424 | operator()(const Cntnr& r_c) const | |
425 | { | |
426 | const stat top_stat = | |
427 | verify_imp(r_c.node_begin(), r_c.node_end()); | |
428 | ||
429 | return (top_stat.first); | |
430 | } | |
431 | ||
432 | #undef PB_ASSOC_CLASS_T_DEC | |
433 | ||
434 | #undef PB_ASSOC_CLASS_C_DEC | |
435 | ||
436 | #endif // #ifndef ORDER_STATISTICS_IMP_HPP |