libstdc++-v3/include/ext/pb_assoc/detail/order_statistics_imp.hpp

   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
  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