contrib/libstdc++/include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   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
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file order_statistics_imp.hpp
  44  * Contains forward declarations for order_statistics_key
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 inline typename PB_DS_CLASS_C_DEC::iterator
  49 PB_DS_CLASS_C_DEC::
  50 find_by_order(size_type order)
  51 {
  52   if (empty())
  53     return (end());
  54
  55   ++order;
  56
  57   node_iterator nd_it = node_begin();
  58
  59   node_iterator end_nd_it = node_end();
  60
  61   while (true)
  62     {
  63       if (order > nd_it.get_metadata())
  64         return (++base_type::rightmost_it(nd_it));
  65
  66       const size_type num_children = nd_it.num_children();
  67
  68       if (num_children == 0)
  69         return (*nd_it);
  70
  71       for (size_type i = 0; i < num_children; ++i)
  72         {
  73           node_iterator child_nd_it = nd_it.get_child(i);
  74
  75           if (order <= child_nd_it.get_metadata())
  76             {
  77               i = num_children;
  78
  79               nd_it = child_nd_it;
  80             }
  81           else
  82             order -= child_nd_it.get_metadata();
  83         }
  84     }
  85 }
  86
  87 PB_DS_CLASS_T_DEC
  88 inline typename PB_DS_CLASS_C_DEC::const_iterator
  89 PB_DS_CLASS_C_DEC::
  90 find_by_order(size_type order) const
  91 {
  92   return (const_cast<PB_DS_CLASS_C_DEC* >(this)->find_by_order(order));
  93 }
  94
  95 PB_DS_CLASS_T_DEC
  96 inline typename PB_DS_CLASS_C_DEC::size_type
  97 PB_DS_CLASS_C_DEC::
  98 order_of_key(const_key_reference r_key) const
  99 {
 100   const E_Access_Traits& r_traits =
 101     const_cast<PB_DS_CLASS_C_DEC* >(this)->get_e_access_traits();
 102
 103   return (order_of_prefix(
 104                           r_traits.begin(r_key),
 105                           r_traits.end(r_key)));
 106 }
 107
 108 PB_DS_CLASS_T_DEC
 109 inline typename PB_DS_CLASS_C_DEC::size_type
 110 PB_DS_CLASS_C_DEC::
 111 order_of_prefix(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) const
 112 {
 113   if (empty())
 114     return (0);
 115
 116   const E_Access_Traits& r_traits =
 117     const_cast<PB_DS_CLASS_C_DEC* >(this)->get_e_access_traits();
 118
 119   const_node_iterator nd_it = node_begin();
 120
 121   const_node_iterator end_nd_it = node_end();
 122
 123   size_type ord = 0;
 124
 125   while (true)
 126     {
 127       const size_type num_children = nd_it.num_children();
 128
 129       if (num_children == 0)
 130         {
 131           const_key_reference r_key =
 132             base_type::extract_key(*(*nd_it));
 133
 134           typename e_access_traits::const_iterator key_b =
 135             r_traits.begin(r_key);
 136
 137           typename e_access_traits::const_iterator key_e =
 138             r_traits.end(r_key);
 139
 140           return ((base_type::less(                    key_b, key_e,  b, e,  r_traits))?
 141                   ord + 1 :
 142                   ord);
 143         }
 144
 145       const_node_iterator next_nd_it = end_nd_it;
 146
 147       size_type i = num_children - 1;
 148
 149       do
 150         {
 151           const_node_iterator child_nd_it = nd_it.get_child(i);
 152
 153           if (next_nd_it != end_nd_it)
 154             ord += child_nd_it.get_metadata();
 155           else if (!base_type::less(
 156                                     b, e,
 157                                     child_nd_it.valid_prefix().first,
 158                                     child_nd_it.valid_prefix().second,
 159                                     r_traits))
 160             next_nd_it = child_nd_it;
 161         }
 162       while (i-- > 0);
 163
 164       if (next_nd_it == end_nd_it)
 165         return (ord);
 166
 167       nd_it = next_nd_it;
 168     }
 169 }
 170
 171 PB_DS_CLASS_T_DEC
 172 inline void
 173 PB_DS_CLASS_C_DEC::
 174 operator()(node_iterator nd_it, const_node_iterator /*end_nd_it*/) const
 175 {
 176   const size_type num_children = nd_it.num_children();
 177
 178   size_type children_rank = 0;
 179
 180   for (size_type i = 0; i < num_children; ++i)
 181     children_rank += nd_it.get_child(i).get_metadata();
 182
 183   const_cast<size_type& >(nd_it.get_metadata()) =(num_children == 0)? 1 : children_rank;
 184 }
 185
 186 PB_DS_CLASS_T_DEC
 187 PB_DS_CLASS_C_DEC::
 188 ~trie_order_statistics_node_update()
 189 { }