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