1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2018 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 pat_trie_/find_fn_imps.hpp 38 * Contains an implementation class for pat_trie. 39 */ 40 41 PB_DS_CLASS_T_DEC 42 inline typename PB_DS_CLASS_C_DEC::point_iterator 43 PB_DS_CLASS_C_DEC:: 44 find(key_const_reference r_key) 45 { 46 PB_DS_ASSERT_VALID((*this)) 47 node_pointer p_nd = find_imp(r_key); 48 49 if (p_nd == 0 || p_nd->m_type != leaf_node) 50 { 51 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 52 return end(); 53 } 54 55 if (synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) 56 { 57 PB_DS_CHECK_KEY_EXISTS(r_key) 58 return iterator(p_nd); 59 } 60 61 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 62 return end(); 63 } 64 65 PB_DS_CLASS_T_DEC 66 inline typename PB_DS_CLASS_C_DEC::point_const_iterator 67 PB_DS_CLASS_C_DEC:: 68 find(key_const_reference r_key) const 69 { 70 PB_DS_ASSERT_VALID((*this)) 71 72 node_const_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); 73 74 if (p_nd == 0 || p_nd->m_type != leaf_node) 75 { 76 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 77 return end(); 78 } 79 80 if (synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(p_nd)->value()), r_key)) 81 { 82 PB_DS_CHECK_KEY_EXISTS(r_key) 83 return const_iterator(const_cast<node_pointer>(p_nd)); 84 } 85 86 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 87 return end(); 88 } 89 90 PB_DS_CLASS_T_DEC 91 inline typename PB_DS_CLASS_C_DEC::node_pointer 92 PB_DS_CLASS_C_DEC:: 93 find_imp(key_const_reference r_key) 94 { 95 if (empty()) 96 return 0; 97 98 typename synth_access_traits::const_iterator b_it = 99 synth_access_traits::begin(r_key); 100 typename synth_access_traits::const_iterator e_it = 101 synth_access_traits::end(r_key); 102 103 node_pointer p_nd = m_p_head->m_p_parent; 104 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 105 106 while (p_nd->m_type != leaf_node) 107 { 108 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 109 node_pointer p_next_nd = static_cast<inode_pointer>(p_nd)->get_child_node(b_it, e_it, this); 110 111 if (p_next_nd == 0) 112 return p_nd; 113 p_nd = p_next_nd; 114 } 115 return p_nd; 116 } 117 118 PB_DS_CLASS_T_DEC 119 inline typename PB_DS_CLASS_C_DEC::node_pointer 120 PB_DS_CLASS_C_DEC:: 121 lower_bound_imp(key_const_reference r_key) 122 { 123 if (empty()) 124 return (m_p_head); 125 126 node_pointer p_nd = m_p_head->m_p_parent; 127 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 128 129 typename PB_DS_CLASS_C_DEC::a_const_iterator b_it = 130 synth_access_traits::begin(r_key); 131 132 typename PB_DS_CLASS_C_DEC::a_const_iterator e_it = 133 synth_access_traits::end(r_key); 134 135 size_type checked_ind = 0; 136 while (true) 137 { 138 if (p_nd->m_type == leaf_node) 139 { 140 if (!synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(p_nd)->value()), r_key)) 141 return p_nd; 142 iterator it(p_nd); 143 ++it; 144 return it.m_p_nd; 145 } 146 147 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 148 const size_type new_checked_ind = 149 static_cast<inode_pointer>(p_nd)->get_e_ind(); 150 151 p_nd = 152 static_cast<inode_pointer>(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); 153 checked_ind = new_checked_ind; 154 } 155 } 156 157 PB_DS_CLASS_T_DEC 158 inline typename PB_DS_CLASS_C_DEC::point_iterator 159 PB_DS_CLASS_C_DEC:: 160 lower_bound(key_const_reference r_key) 161 { return point_iterator(lower_bound_imp(r_key)); } 162 163 PB_DS_CLASS_T_DEC 164 inline typename PB_DS_CLASS_C_DEC::point_const_iterator 165 PB_DS_CLASS_C_DEC:: 166 lower_bound(key_const_reference r_key) const 167 { 168 return point_const_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key)); 169 } 170 171 PB_DS_CLASS_T_DEC 172 inline typename PB_DS_CLASS_C_DEC::point_iterator 173 PB_DS_CLASS_C_DEC:: 174 upper_bound(key_const_reference r_key) 175 { 176 point_iterator l_bound_it = lower_bound(r_key); 177 178 _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 179 !synth_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 180 r_key)); 181 182 if (l_bound_it == end() || 183 synth_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 184 return l_bound_it; 185 186 return ++l_bound_it; 187 } 188 189 PB_DS_CLASS_T_DEC 190 inline typename PB_DS_CLASS_C_DEC::point_const_iterator 191 PB_DS_CLASS_C_DEC:: 192 upper_bound(key_const_reference r_key) const 193 { 194 point_const_iterator l_bound_it = lower_bound(r_key); 195 196 _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 197 !synth_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 198 r_key)); 199 200 if (l_bound_it == end() || 201 synth_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 202 return l_bound_it; 203 return ++l_bound_it; 204 } 205 206 PB_DS_CLASS_T_DEC 207 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 208 PB_DS_CLASS_C_DEC:: 209 pref_begin(node_const_pointer p_nd) 210 { 211 if (p_nd->m_type == leaf_node) 212 return (synth_access_traits::begin(PB_DS_V2F(static_cast<leaf_const_pointer>(p_nd)->value()))); 213 214 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 215 return static_cast<inode_const_pointer>(p_nd)->pref_b_it(); 216 } 217 218 PB_DS_CLASS_T_DEC 219 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 220 PB_DS_CLASS_C_DEC:: 221 pref_end(node_const_pointer p_nd) 222 { 223 if (p_nd->m_type == leaf_node) 224 return (synth_access_traits::end(PB_DS_V2F(static_cast<leaf_const_pointer>(p_nd)->value()))); 225 226 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 227 return static_cast<inode_const_pointer>(p_nd)->pref_e_it(); 228 } 229 230 PB_DS_CLASS_T_DEC 231 inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer 232 PB_DS_CLASS_C_DEC:: 233 leftmost_descendant(node_const_pointer p_nd) 234 { 235 if (p_nd->m_type == leaf_node) 236 return static_cast<leaf_const_pointer>(p_nd); 237 return static_cast<inode_const_pointer>(p_nd)->leftmost_descendant(); 238 } 239 240 PB_DS_CLASS_T_DEC 241 inline typename PB_DS_CLASS_C_DEC::leaf_pointer 242 PB_DS_CLASS_C_DEC:: 243 leftmost_descendant(node_pointer p_nd) 244 { 245 if (p_nd->m_type == leaf_node) 246 return static_cast<leaf_pointer>(p_nd); 247 return static_cast<inode_pointer>(p_nd)->leftmost_descendant(); 248 } 249 250 PB_DS_CLASS_T_DEC 251 inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer 252 PB_DS_CLASS_C_DEC:: 253 rightmost_descendant(node_const_pointer p_nd) 254 { 255 if (p_nd->m_type == leaf_node) 256 return static_cast<leaf_const_pointer>(p_nd); 257 return static_cast<inode_const_pointer>(p_nd)->rightmost_descendant(); 258 } 259 260 PB_DS_CLASS_T_DEC 261 inline typename PB_DS_CLASS_C_DEC::leaf_pointer 262 PB_DS_CLASS_C_DEC:: 263 rightmost_descendant(node_pointer p_nd) 264 { 265 if (p_nd->m_type == leaf_node) 266 return static_cast<leaf_pointer>(p_nd); 267 return static_cast<inode_pointer>(p_nd)->rightmost_descendant(); 268 } 269 270