1// -*- C++ -*- 2 3// Copyright (C) 2005-2015 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 41PB_DS_CLASS_T_DEC 42inline typename PB_DS_CLASS_C_DEC::point_iterator 43PB_DS_CLASS_C_DEC:: 44find(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 65PB_DS_CLASS_T_DEC 66inline typename PB_DS_CLASS_C_DEC::point_const_iterator 67PB_DS_CLASS_C_DEC:: 68find(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 90PB_DS_CLASS_T_DEC 91inline typename PB_DS_CLASS_C_DEC::node_pointer 92PB_DS_CLASS_C_DEC:: 93find_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 118PB_DS_CLASS_T_DEC 119inline typename PB_DS_CLASS_C_DEC::node_pointer 120PB_DS_CLASS_C_DEC:: 121lower_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 157PB_DS_CLASS_T_DEC 158inline typename PB_DS_CLASS_C_DEC::point_iterator 159PB_DS_CLASS_C_DEC:: 160lower_bound(key_const_reference r_key) 161{ return point_iterator(lower_bound_imp(r_key)); } 162 163PB_DS_CLASS_T_DEC 164inline typename PB_DS_CLASS_C_DEC::point_const_iterator 165PB_DS_CLASS_C_DEC:: 166lower_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 171PB_DS_CLASS_T_DEC 172inline typename PB_DS_CLASS_C_DEC::point_iterator 173PB_DS_CLASS_C_DEC:: 174upper_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 189PB_DS_CLASS_T_DEC 190inline typename PB_DS_CLASS_C_DEC::point_const_iterator 191PB_DS_CLASS_C_DEC:: 192upper_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 206PB_DS_CLASS_T_DEC 207inline typename PB_DS_CLASS_C_DEC::a_const_iterator 208PB_DS_CLASS_C_DEC:: 209pref_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 218PB_DS_CLASS_T_DEC 219inline typename PB_DS_CLASS_C_DEC::a_const_iterator 220PB_DS_CLASS_C_DEC:: 221pref_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 230PB_DS_CLASS_T_DEC 231inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer 232PB_DS_CLASS_C_DEC:: 233leftmost_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 240PB_DS_CLASS_T_DEC 241inline typename PB_DS_CLASS_C_DEC::leaf_pointer 242PB_DS_CLASS_C_DEC:: 243leftmost_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 250PB_DS_CLASS_T_DEC 251inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer 252PB_DS_CLASS_C_DEC:: 253rightmost_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 260PB_DS_CLASS_T_DEC 261inline typename PB_DS_CLASS_C_DEC::leaf_pointer 262PB_DS_CLASS_C_DEC:: 263rightmost_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