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 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 56PB_ASSOC_CLASS_T_DEC 57inline 58PB_ASSOC_CLASS_C_DEC:: 59order_statistics_key(const_key_reference r_key) : 60 m_key(r_key), 61 m_rank(1) 62{ } 63 64PB_ASSOC_CLASS_T_DEC 65inline 66PB_ASSOC_CLASS_C_DEC:: 67operator typename PB_ASSOC_CLASS_C_DEC::key_reference() 68{ 69 return (m_key); 70} 71 72PB_ASSOC_CLASS_T_DEC 73inline 74PB_ASSOC_CLASS_C_DEC:: 75operator 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 92PB_ASSOC_CLASS_T_DEC 93inline 94PB_ASSOC_CLASS_C_DEC:: 95order_statistics_key_cmp() 96{ } 97 98PB_ASSOC_CLASS_T_DEC 99inline 100PB_ASSOC_CLASS_C_DEC:: 101order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn) : 102 Cmp_Fn(r_cmp_fn) 103{ } 104 105PB_ASSOC_CLASS_T_DEC 106inline bool 107PB_ASSOC_CLASS_C_DEC:: 108operator()(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 113PB_ASSOC_CLASS_T_DEC 114inline typename PB_ASSOC_CLASS_C_DEC::cmp_fn& 115PB_ASSOC_CLASS_C_DEC:: 116get_cmp_fn() 117{ 118 return (*this); 119} 120 121PB_ASSOC_CLASS_T_DEC 122inline const typename PB_ASSOC_CLASS_C_DEC::cmp_fn& 123PB_ASSOC_CLASS_C_DEC:: 124get_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 141PB_ASSOC_CLASS_T_DEC 142inline void 143PB_ASSOC_CLASS_C_DEC:: 144operator()(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 165PB_ASSOC_CLASS_T_DEC 166inline void 167PB_ASSOC_CLASS_C_DEC:: 168swap(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 182PB_ASSOC_CLASS_T_DEC 183inline typename PB_ASSOC_CLASS_C_DEC::iterator 184PB_ASSOC_CLASS_C_DEC:: 185operator()(Cntnr& r_c, size_type order) const 186{ 187 return find(r_c, order); 188} 189 190PB_ASSOC_CLASS_T_DEC 191inline typename PB_ASSOC_CLASS_C_DEC::const_iterator 192PB_ASSOC_CLASS_C_DEC:: 193operator()(const Cntnr& r_c, size_type order) const 194{ 195 return find(r_c, order); 196} 197 198PB_ASSOC_CLASS_T_DEC 199inline typename PB_ASSOC_CLASS_C_DEC::const_iterator 200PB_ASSOC_CLASS_C_DEC:: 201find(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 251PB_ASSOC_CLASS_T_DEC 252inline typename PB_ASSOC_CLASS_C_DEC::iterator 253PB_ASSOC_CLASS_C_DEC:: 254find(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 316PB_ASSOC_CLASS_T_DEC 317inline typename PB_ASSOC_CLASS_C_DEC::size_type 318PB_ASSOC_CLASS_C_DEC:: 319operator()(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 373template<class Cntnr, class Allocator = std::allocator<char> > 374class order_statistics_key_verifier 375{ 376public: 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 387public: 388 bool 389 operator()(const Cntnr& r_c) const; 390 391private: 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 398private: 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 421PB_ASSOC_CLASS_T_DEC 422bool 423PB_ASSOC_CLASS_C_DEC:: 424operator()(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 437