1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file find_fn_imps.hpp 44169691Skan * Contains an implementation class for bin_search_tree_. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skaninline typename PB_DS_CLASS_C_DEC::point_iterator 49169691SkanPB_DS_CLASS_C_DEC:: 50169691Skanfind(const_key_reference r_key) 51169691Skan{ 52169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 53169691Skan node_pointer p_nd = find_imp(r_key); 54169691Skan 55169691Skan if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) 56169691Skan { 57169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 58169691Skan return end(); 59169691Skan } 60169691Skan 61169691Skan if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) 62169691Skan { 63169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 64169691Skan return iterator(p_nd); 65169691Skan } 66169691Skan 67169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 68169691Skan return end(); 69169691Skan} 70169691Skan 71169691SkanPB_DS_CLASS_T_DEC 72169691Skaninline typename PB_DS_CLASS_C_DEC::const_point_iterator 73169691SkanPB_DS_CLASS_C_DEC:: 74169691Skanfind(const_key_reference r_key) const 75169691Skan{ 76169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 77169691Skan 78169691Skan const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); 79169691Skan 80169691Skan if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) 81169691Skan { 82169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 83169691Skan return end(); 84169691Skan } 85169691Skan 86169691Skan if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) 87169691Skan { 88169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 89169691Skan return const_iterator(const_cast<node_pointer>(p_nd)); 90169691Skan } 91169691Skan 92169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 93169691Skan return end(); 94169691Skan} 95169691Skan 96169691SkanPB_DS_CLASS_T_DEC 97169691Skaninline typename PB_DS_CLASS_C_DEC::node_pointer 98169691SkanPB_DS_CLASS_C_DEC:: 99169691Skanfind_imp(const_key_reference r_key) 100169691Skan{ 101169691Skan if (empty()) 102169691Skan return (NULL); 103169691Skan 104169691Skan typename synth_e_access_traits::const_iterator b_it = 105169691Skan synth_e_access_traits::begin(r_key); 106169691Skan typename synth_e_access_traits::const_iterator e_it = 107169691Skan synth_e_access_traits::end(r_key); 108169691Skan 109169691Skan node_pointer p_nd = m_p_head->m_p_parent; 110169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 111169691Skan 112169691Skan while (p_nd->m_type != pat_trie_leaf_node_type) 113169691Skan { 114169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 115169691Skan node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it, e_it, this); 116169691Skan 117169691Skan if (p_next_nd == NULL) 118169691Skan return p_nd; 119169691Skan p_nd = p_next_nd; 120169691Skan } 121169691Skan return p_nd; 122169691Skan} 123169691Skan 124169691SkanPB_DS_CLASS_T_DEC 125169691Skaninline typename PB_DS_CLASS_C_DEC::node_pointer 126169691SkanPB_DS_CLASS_C_DEC:: 127169691Skanlower_bound_imp(const_key_reference r_key) 128169691Skan{ 129169691Skan if (empty()) 130169691Skan return (m_p_head); 131169691Skan 132169691Skan node_pointer p_nd = m_p_head->m_p_parent; 133169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 134169691Skan 135169691Skan typename PB_DS_CLASS_C_DEC::const_e_iterator b_it = 136169691Skan synth_e_access_traits::begin(r_key); 137169691Skan 138169691Skan typename PB_DS_CLASS_C_DEC::const_e_iterator e_it = 139169691Skan synth_e_access_traits::end(r_key); 140169691Skan 141169691Skan size_type checked_ind = 0; 142169691Skan while (true) 143169691Skan { 144169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 145169691Skan { 146169691Skan if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) 147169691Skan return p_nd; 148169691Skan iterator it(p_nd); 149169691Skan ++it; 150169691Skan return it.m_p_nd; 151169691Skan } 152169691Skan 153169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 154169691Skan const size_type new_checked_ind = 155169691Skan static_cast<internal_node_pointer>(p_nd)->get_e_ind(); 156169691Skan 157169691Skan p_nd = 158169691Skan static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); 159169691Skan checked_ind = new_checked_ind; 160169691Skan } 161169691Skan} 162169691Skan 163169691SkanPB_DS_CLASS_T_DEC 164169691Skaninline typename PB_DS_CLASS_C_DEC::point_iterator 165169691SkanPB_DS_CLASS_C_DEC:: 166169691Skanlower_bound(const_key_reference r_key) 167169691Skan{ return point_iterator(lower_bound_imp(r_key)); } 168169691Skan 169169691SkanPB_DS_CLASS_T_DEC 170169691Skaninline typename PB_DS_CLASS_C_DEC::const_point_iterator 171169691SkanPB_DS_CLASS_C_DEC:: 172169691Skanlower_bound(const_key_reference r_key) const 173169691Skan{ 174169691Skan return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key)); 175169691Skan} 176169691Skan 177169691SkanPB_DS_CLASS_T_DEC 178169691Skaninline typename PB_DS_CLASS_C_DEC::point_iterator 179169691SkanPB_DS_CLASS_C_DEC:: 180169691Skanupper_bound(const_key_reference r_key) 181169691Skan{ 182169691Skan point_iterator l_bound_it = lower_bound(r_key); 183169691Skan 184169691Skan _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 185169691Skan !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 186169691Skan r_key)); 187169691Skan 188169691Skan if (l_bound_it == end() || 189169691Skan synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 190169691Skan return l_bound_it; 191169691Skan 192169691Skan return ++l_bound_it; 193169691Skan} 194169691Skan 195169691SkanPB_DS_CLASS_T_DEC 196169691Skaninline typename PB_DS_CLASS_C_DEC::const_point_iterator 197169691SkanPB_DS_CLASS_C_DEC:: 198169691Skanupper_bound(const_key_reference r_key) const 199169691Skan{ 200169691Skan const_point_iterator l_bound_it = lower_bound(r_key); 201169691Skan 202169691Skan _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 203169691Skan !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 204169691Skan r_key)); 205169691Skan 206169691Skan if (l_bound_it == end() || 207169691Skan synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 208169691Skan return l_bound_it; 209169691Skan return ++l_bound_it; 210169691Skan} 211169691Skan 212169691SkanPB_DS_CLASS_T_DEC 213169691Skaninline typename PB_DS_CLASS_C_DEC::const_e_iterator 214169691SkanPB_DS_CLASS_C_DEC:: 215169691Skanpref_begin(const_node_pointer p_nd) 216169691Skan{ 217169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 218169691Skan return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); 219169691Skan 220169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 221169691Skan return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it(); 222169691Skan} 223169691Skan 224169691SkanPB_DS_CLASS_T_DEC 225169691Skaninline typename PB_DS_CLASS_C_DEC::const_e_iterator 226169691SkanPB_DS_CLASS_C_DEC:: 227169691Skanpref_end(const_node_pointer p_nd) 228169691Skan{ 229169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 230169691Skan return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); 231169691Skan 232169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 233169691Skan return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it(); 234169691Skan} 235169691Skan 236169691SkanPB_DS_CLASS_T_DEC 237169691Skaninline typename PB_DS_CLASS_C_DEC::const_leaf_pointer 238169691SkanPB_DS_CLASS_C_DEC:: 239169691Skanleftmost_descendant(const_node_pointer p_nd) 240169691Skan{ 241169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 242169691Skan return static_cast<const_leaf_pointer>(p_nd); 243169691Skan return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant(); 244169691Skan} 245169691Skan 246169691SkanPB_DS_CLASS_T_DEC 247169691Skaninline typename PB_DS_CLASS_C_DEC::leaf_pointer 248169691SkanPB_DS_CLASS_C_DEC:: 249169691Skanleftmost_descendant(node_pointer p_nd) 250169691Skan{ 251169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 252169691Skan return static_cast<leaf_pointer>(p_nd); 253169691Skan return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); 254169691Skan} 255169691Skan 256169691SkanPB_DS_CLASS_T_DEC 257169691Skaninline typename PB_DS_CLASS_C_DEC::const_leaf_pointer 258169691SkanPB_DS_CLASS_C_DEC:: 259169691Skanrightmost_descendant(const_node_pointer p_nd) 260169691Skan{ 261169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 262169691Skan return static_cast<const_leaf_pointer>(p_nd); 263169691Skan return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant(); 264169691Skan} 265169691Skan 266169691SkanPB_DS_CLASS_T_DEC 267169691Skaninline typename PB_DS_CLASS_C_DEC::leaf_pointer 268169691SkanPB_DS_CLASS_C_DEC:: 269169691Skanrightmost_descendant(node_pointer p_nd) 270169691Skan{ 271169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 272169691Skan return static_cast<leaf_pointer>(p_nd); 273169691Skan return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); 274169691Skan} 275169691Skan 276