1// -*- C++ -*- 2 3// Copyright (C) 2005-2020 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 43PB_DS_CLASS_T_DEC 44inline typename PB_DS_CLASS_C_DEC::point_iterator 45PB_DS_CLASS_C_DEC:: 46find(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 67PB_DS_CLASS_T_DEC 68inline typename PB_DS_CLASS_C_DEC::point_const_iterator 69PB_DS_CLASS_C_DEC:: 70find(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 92PB_DS_CLASS_T_DEC 93inline typename PB_DS_CLASS_C_DEC::node_pointer 94PB_DS_CLASS_C_DEC:: 95find_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 120PB_DS_CLASS_T_DEC 121inline typename PB_DS_CLASS_C_DEC::node_pointer 122PB_DS_CLASS_C_DEC:: 123lower_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 159PB_DS_CLASS_T_DEC 160inline typename PB_DS_CLASS_C_DEC::point_iterator 161PB_DS_CLASS_C_DEC:: 162lower_bound(key_const_reference r_key) 163{ return point_iterator(lower_bound_imp(r_key)); } 164 165PB_DS_CLASS_T_DEC 166inline typename PB_DS_CLASS_C_DEC::point_const_iterator 167PB_DS_CLASS_C_DEC:: 168lower_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 173PB_DS_CLASS_T_DEC 174inline typename PB_DS_CLASS_C_DEC::point_iterator 175PB_DS_CLASS_C_DEC:: 176upper_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 191PB_DS_CLASS_T_DEC 192inline typename PB_DS_CLASS_C_DEC::point_const_iterator 193PB_DS_CLASS_C_DEC:: 194upper_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 208PB_DS_CLASS_T_DEC 209inline typename PB_DS_CLASS_C_DEC::a_const_iterator 210PB_DS_CLASS_C_DEC:: 211pref_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 220PB_DS_CLASS_T_DEC 221inline typename PB_DS_CLASS_C_DEC::a_const_iterator 222PB_DS_CLASS_C_DEC:: 223pref_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 232PB_DS_CLASS_T_DEC 233inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer 234PB_DS_CLASS_C_DEC:: 235leftmost_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 242PB_DS_CLASS_T_DEC 243inline typename PB_DS_CLASS_C_DEC::leaf_pointer 244PB_DS_CLASS_C_DEC:: 245leftmost_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 252PB_DS_CLASS_T_DEC 253inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer 254PB_DS_CLASS_C_DEC:: 255rightmost_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 262PB_DS_CLASS_T_DEC 263inline typename PB_DS_CLASS_C_DEC::leaf_pointer 264PB_DS_CLASS_C_DEC:: 265rightmost_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 273