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