libstdc++
trie_policy/order_statistics_imp.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file trie_policy/order_statistics_imp.hpp
00038  * Contains forward declarations for order_statistics_key
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 inline typename PB_DS_CLASS_C_DEC::iterator
00043 PB_DS_CLASS_C_DEC::
00044 find_by_order(size_type order)
00045 {
00046   if (empty())
00047     return end();
00048 
00049   ++order;
00050   node_iterator nd_it = node_begin();
00051 
00052   while (true)
00053     {
00054       if (order > nd_it.get_metadata())
00055     return ++base_type::rightmost_it(nd_it);
00056 
00057       const size_type num_children = nd_it.num_children();
00058       if (num_children == 0)
00059     return *nd_it;
00060 
00061       for (size_type i = 0; i < num_children; ++i)
00062     {
00063       node_iterator child_nd_it = nd_it.get_child(i);
00064       if (order <= child_nd_it.get_metadata())
00065         {
00066           i = num_children;
00067           nd_it = child_nd_it;
00068         }
00069       else
00070         order -= child_nd_it.get_metadata();
00071     }
00072     }
00073 }
00074 
00075 PB_DS_CLASS_T_DEC
00076 inline typename PB_DS_CLASS_C_DEC::const_iterator
00077 PB_DS_CLASS_C_DEC::
00078 find_by_order(size_type order) const
00079 { return const_cast<PB_DS_CLASS_C_DEC*>(this)->find_by_order(order); }
00080 
00081 PB_DS_CLASS_T_DEC
00082 inline typename PB_DS_CLASS_C_DEC::size_type
00083 PB_DS_CLASS_C_DEC::
00084 order_of_key(key_const_reference r_key) const
00085 {
00086   const _ATraits& r_traits =
00087     const_cast<PB_DS_CLASS_C_DEC* >(this)->get_access_traits();
00088 
00089   return order_of_prefix(r_traits.begin(r_key), r_traits.end(r_key));
00090 }
00091 
00092 PB_DS_CLASS_T_DEC
00093 inline typename PB_DS_CLASS_C_DEC::size_type
00094 PB_DS_CLASS_C_DEC::
00095 order_of_prefix(typename access_traits::const_iterator b,
00096         typename access_traits::const_iterator e) const
00097 {
00098   if (empty())
00099     return 0;
00100 
00101   const _ATraits& r_traits =
00102     const_cast<PB_DS_CLASS_C_DEC*>(this)->get_access_traits();
00103 
00104   node_const_iterator nd_it = node_begin();
00105   node_const_iterator end_nd_it = node_end();
00106   size_type ord = 0;
00107 
00108   while (true)
00109     {
00110       const size_type num_children = nd_it.num_children();
00111       if (num_children == 0)
00112     {
00113       key_const_reference r_key = base_type::extract_key(*(*nd_it));
00114       typename access_traits::const_iterator key_b =
00115         r_traits.begin(r_key);
00116 
00117       typename access_traits::const_iterator key_e =
00118         r_traits.end(r_key);
00119 
00120       return (base_type::less(key_b, key_e,  b, e,  r_traits)) ?
00121           ord + 1 : ord;
00122     }
00123 
00124       node_const_iterator next_nd_it = end_nd_it;
00125       size_type i = num_children - 1;
00126 
00127       do
00128     {
00129       node_const_iterator child_nd_it = nd_it.get_child(i);
00130 
00131       if (next_nd_it != end_nd_it)
00132         ord += child_nd_it.get_metadata();
00133       else if (!base_type::less(b, e,
00134                     child_nd_it.valid_prefix().first,
00135                     child_nd_it.valid_prefix().second,
00136                     r_traits))
00137         next_nd_it = child_nd_it;
00138     }
00139       while (i-- > 0);
00140 
00141       if (next_nd_it == end_nd_it)
00142     return ord;
00143 
00144       nd_it = next_nd_it;
00145     }
00146 }
00147 
00148 PB_DS_CLASS_T_DEC
00149 inline void
00150 PB_DS_CLASS_C_DEC::
00151 operator()(node_iterator nd_it, node_const_iterator /*end_nd_it*/) const
00152 {
00153   const size_type num_children = nd_it.num_children();
00154   size_type children_rank = 0;
00155   for (size_type i = 0; i < num_children; ++i)
00156     children_rank += nd_it.get_child(i).get_metadata();
00157 
00158   const size_type res = (num_children == 0) ? 1 : children_rank;
00159   const_cast<size_type&>(nd_it.get_metadata()) = res;
00160 }