1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file find_fn_imps.hpp 44 * Contains an implementation class for bin_search_tree_. 45 */ 46 47PB_DS_CLASS_T_DEC 48inline typename PB_DS_CLASS_C_DEC::point_iterator 49PB_DS_CLASS_C_DEC:: 50find(const_key_reference r_key) 51{ 52 _GLIBCXX_DEBUG_ONLY(assert_valid();) 53 node_pointer p_nd = find_imp(r_key); 54 55 if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) 56 { 57 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 58 return end(); 59 } 60 61 if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) 62 { 63 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 64 return iterator(p_nd); 65 } 66 67 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 68 return end(); 69} 70 71PB_DS_CLASS_T_DEC 72inline typename PB_DS_CLASS_C_DEC::const_point_iterator 73PB_DS_CLASS_C_DEC:: 74find(const_key_reference r_key) const 75{ 76 _GLIBCXX_DEBUG_ONLY(assert_valid();) 77 78 const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); 79 80 if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) 81 { 82 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 83 return end(); 84 } 85 86 if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) 87 { 88 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 89 return const_iterator(const_cast<node_pointer>(p_nd)); 90 } 91 92 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 93 return end(); 94} 95 96PB_DS_CLASS_T_DEC 97inline typename PB_DS_CLASS_C_DEC::node_pointer 98PB_DS_CLASS_C_DEC:: 99find_imp(const_key_reference r_key) 100{ 101 if (empty()) 102 return (NULL); 103 104 typename synth_e_access_traits::const_iterator b_it = 105 synth_e_access_traits::begin(r_key); 106 typename synth_e_access_traits::const_iterator e_it = 107 synth_e_access_traits::end(r_key); 108 109 node_pointer p_nd = m_p_head->m_p_parent; 110 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 111 112 while (p_nd->m_type != pat_trie_leaf_node_type) 113 { 114 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 115 node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it, e_it, this); 116 117 if (p_next_nd == NULL) 118 return p_nd; 119 p_nd = p_next_nd; 120 } 121 return p_nd; 122} 123 124PB_DS_CLASS_T_DEC 125inline typename PB_DS_CLASS_C_DEC::node_pointer 126PB_DS_CLASS_C_DEC:: 127lower_bound_imp(const_key_reference r_key) 128{ 129 if (empty()) 130 return (m_p_head); 131 132 node_pointer p_nd = m_p_head->m_p_parent; 133 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 134 135 typename PB_DS_CLASS_C_DEC::const_e_iterator b_it = 136 synth_e_access_traits::begin(r_key); 137 138 typename PB_DS_CLASS_C_DEC::const_e_iterator e_it = 139 synth_e_access_traits::end(r_key); 140 141 size_type checked_ind = 0; 142 while (true) 143 { 144 if (p_nd->m_type == pat_trie_leaf_node_type) 145 { 146 if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) 147 return p_nd; 148 iterator it(p_nd); 149 ++it; 150 return it.m_p_nd; 151 } 152 153 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 154 const size_type new_checked_ind = 155 static_cast<internal_node_pointer>(p_nd)->get_e_ind(); 156 157 p_nd = 158 static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); 159 checked_ind = new_checked_ind; 160 } 161} 162 163PB_DS_CLASS_T_DEC 164inline typename PB_DS_CLASS_C_DEC::point_iterator 165PB_DS_CLASS_C_DEC:: 166lower_bound(const_key_reference r_key) 167{ return point_iterator(lower_bound_imp(r_key)); } 168 169PB_DS_CLASS_T_DEC 170inline typename PB_DS_CLASS_C_DEC::const_point_iterator 171PB_DS_CLASS_C_DEC:: 172lower_bound(const_key_reference r_key) const 173{ 174 return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key)); 175} 176 177PB_DS_CLASS_T_DEC 178inline typename PB_DS_CLASS_C_DEC::point_iterator 179PB_DS_CLASS_C_DEC:: 180upper_bound(const_key_reference r_key) 181{ 182 point_iterator l_bound_it = lower_bound(r_key); 183 184 _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 185 !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 186 r_key)); 187 188 if (l_bound_it == end() || 189 synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 190 return l_bound_it; 191 192 return ++l_bound_it; 193} 194 195PB_DS_CLASS_T_DEC 196inline typename PB_DS_CLASS_C_DEC::const_point_iterator 197PB_DS_CLASS_C_DEC:: 198upper_bound(const_key_reference r_key) const 199{ 200 const_point_iterator l_bound_it = lower_bound(r_key); 201 202 _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 203 !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 204 r_key)); 205 206 if (l_bound_it == end() || 207 synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 208 return l_bound_it; 209 return ++l_bound_it; 210} 211 212PB_DS_CLASS_T_DEC 213inline typename PB_DS_CLASS_C_DEC::const_e_iterator 214PB_DS_CLASS_C_DEC:: 215pref_begin(const_node_pointer p_nd) 216{ 217 if (p_nd->m_type == pat_trie_leaf_node_type) 218 return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); 219 220 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 221 return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it(); 222} 223 224PB_DS_CLASS_T_DEC 225inline typename PB_DS_CLASS_C_DEC::const_e_iterator 226PB_DS_CLASS_C_DEC:: 227pref_end(const_node_pointer p_nd) 228{ 229 if (p_nd->m_type == pat_trie_leaf_node_type) 230 return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); 231 232 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 233 return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it(); 234} 235 236PB_DS_CLASS_T_DEC 237inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer 238PB_DS_CLASS_C_DEC:: 239leftmost_descendant(const_node_pointer p_nd) 240{ 241 if (p_nd->m_type == pat_trie_leaf_node_type) 242 return static_cast<const_leaf_pointer>(p_nd); 243 return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant(); 244} 245 246PB_DS_CLASS_T_DEC 247inline typename PB_DS_CLASS_C_DEC::leaf_pointer 248PB_DS_CLASS_C_DEC:: 249leftmost_descendant(node_pointer p_nd) 250{ 251 if (p_nd->m_type == pat_trie_leaf_node_type) 252 return static_cast<leaf_pointer>(p_nd); 253 return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); 254} 255 256PB_DS_CLASS_T_DEC 257inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer 258PB_DS_CLASS_C_DEC:: 259rightmost_descendant(const_node_pointer p_nd) 260{ 261 if (p_nd->m_type == pat_trie_leaf_node_type) 262 return static_cast<const_leaf_pointer>(p_nd); 263 return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant(); 264} 265 266PB_DS_CLASS_T_DEC 267inline typename PB_DS_CLASS_C_DEC::leaf_pointer 268PB_DS_CLASS_C_DEC:: 269rightmost_descendant(node_pointer p_nd) 270{ 271 if (p_nd->m_type == pat_trie_leaf_node_type) 272 return static_cast<leaf_pointer>(p_nd); 273 return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); 274} 275 276