find_fn_imps.hpp revision 272461
115885Sjulian// -*- C++ -*- 215885Sjulian 315885Sjulian// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 415885Sjulian// 515885Sjulian// This file is part of the GNU ISO C++ Library. This library is free 615885Sjulian// software; you can redistribute it and/or modify it under the terms 715885Sjulian// of the GNU General Public License as published by the Free Software 815885Sjulian// Foundation; either version 2, or (at your option) any later 929024Sbde// version. 1015885Sjulian 1115885Sjulian// This library is distributed in the hope that it will be useful, but 1215885Sjulian// WITHOUT ANY WARRANTY; without even the implied warranty of 1315885Sjulian// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1415885Sjulian// General Public License for more details. 1515885Sjulian 1615885Sjulian// You should have received a copy of the GNU General Public License 1718207Sbde// along with this library; see the file COPYING. If not, write to 1818207Sbde// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1918207Sbde// MA 02111-1307, USA. 2015885Sjulian 2115885Sjulian// As a special exception, you may use this file as part of a free 2215885Sjulian// software library without restriction. Specifically, if other files 2328270Swollman// instantiate templates or use macros or inline functions from this 2428270Swollman// file, or you compile this file and link it with other files to 2528270Swollman// produce an executable, this file does not by itself cause the 2628270Swollman// resulting executable to be covered by the GNU General Public 2728270Swollman// License. This exception does not however invalidate any other 2828270Swollman// reasons why the executable file might be covered by the GNU General 2928270Swollman// Public License. 3015885Sjulian 3115885Sjulian// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3215885Sjulian 3333181Seivind// Permission to use, copy, modify, sell, and distribute this software 3433181Seivind// is hereby granted without fee, provided that the above copyright 3515885Sjulian// notice appears in all copies, and that both that copyright notice 3625791Sjulian// and this permission notice appear in supporting documentation. None 3725791Sjulian// of the above authors, nor IBM Haifa Research Laboratories, make any 3825791Sjulian// representation about the suitability of this software for any 3915885Sjulian// purpose. It is provided "as is" without express or implied 4025791Sjulian// warranty. 4125791Sjulian 4225791Sjulian/** 4325791Sjulian * @file find_fn_imps.hpp 4415885Sjulian * Contains an implementation class for bin_search_tree_. 4525791Sjulian */ 4615885Sjulian 4725791SjulianPB_DS_CLASS_T_DEC 4815885Sjulianinline typename PB_DS_CLASS_C_DEC::point_iterator 4925791SjulianPB_DS_CLASS_C_DEC:: 5025791Sjulianfind(const_key_reference r_key) 5125791Sjulian{ 5225791Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 5325791Sjulian node_pointer p_nd = find_imp(r_key); 5425791Sjulian 5515885Sjulian if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) 5625791Sjulian { 5725791Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 5815885Sjulian return end(); 5925791Sjulian } 6025791Sjulian 6125791Sjulian if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) 6225791Sjulian { 6325791Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 6425791Sjulian return iterator(p_nd); 6525791Sjulian } 6625791Sjulian 6725791Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 6825791Sjulian return end(); 6925791Sjulian} 7015885Sjulian 7125791SjulianPB_DS_CLASS_T_DEC 7225791Sjulianinline typename PB_DS_CLASS_C_DEC::const_point_iterator 7325791SjulianPB_DS_CLASS_C_DEC:: 7415885Sjulianfind(const_key_reference r_key) const 7525791Sjulian{ 7628270Swollman _GLIBCXX_DEBUG_ONLY(assert_valid();) 7725791Sjulian 7825791Sjulian const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); 7925791Sjulian 8025791Sjulian if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) 8125791Sjulian { 8225791Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 8325791Sjulian return end(); 8425791Sjulian } 8525791Sjulian 8625791Sjulian if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) 8728270Swollman { 8825791Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 8925791Sjulian return const_iterator(const_cast<node_pointer>(p_nd)); 9025791Sjulian } 9115885Sjulian 9225791Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 9328270Swollman return end(); 9425791Sjulian} 9525791Sjulian 9625791SjulianPB_DS_CLASS_T_DEC 9725791Sjulianinline typename PB_DS_CLASS_C_DEC::node_pointer 9825791SjulianPB_DS_CLASS_C_DEC:: 9925791Sjulianfind_imp(const_key_reference r_key) 10025791Sjulian{ 10125791Sjulian if (empty()) 10225791Sjulian return (NULL); 10315885Sjulian 10415885Sjulian typename synth_e_access_traits::const_iterator b_it = 10525791Sjulian synth_e_access_traits::begin(r_key); 10615885Sjulian typename synth_e_access_traits::const_iterator e_it = 10715885Sjulian synth_e_access_traits::end(r_key); 10825791Sjulian 10925791Sjulian node_pointer p_nd = m_p_head->m_p_parent; 11025791Sjulian _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 11115885Sjulian 11215885Sjulian while (p_nd->m_type != pat_trie_leaf_node_type) 11325791Sjulian { 11425791Sjulian _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 11515885Sjulian node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it, e_it, this); 11625791Sjulian 11725791Sjulian if (p_next_nd == NULL) 11825791Sjulian return p_nd; 11925791Sjulian p_nd = p_next_nd; 12025791Sjulian } 12125791Sjulian return p_nd; 12225791Sjulian} 12325791Sjulian 12425791SjulianPB_DS_CLASS_T_DEC 12525791Sjulianinline typename PB_DS_CLASS_C_DEC::node_pointer 12625791SjulianPB_DS_CLASS_C_DEC:: 12715885Sjulianlower_bound_imp(const_key_reference r_key) 12825791Sjulian{ 12915885Sjulian if (empty()) 13025791Sjulian return (m_p_head); 13125791Sjulian 13215885Sjulian node_pointer p_nd = m_p_head->m_p_parent; 13325791Sjulian _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 13425791Sjulian 13515885Sjulian typename PB_DS_CLASS_C_DEC::const_e_iterator b_it = 13625791Sjulian synth_e_access_traits::begin(r_key); 13725791Sjulian 13815885Sjulian typename PB_DS_CLASS_C_DEC::const_e_iterator e_it = 13925791Sjulian synth_e_access_traits::end(r_key); 14025791Sjulian 14125791Sjulian size_type checked_ind = 0; 14225791Sjulian while (true) 14341591Sarchie { 14425791Sjulian if (p_nd->m_type == pat_trie_leaf_node_type) 14525791Sjulian { 14625791Sjulian if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) 14725791Sjulian return p_nd; 14815885Sjulian iterator it(p_nd); 14925791Sjulian ++it; 15025791Sjulian return it.m_p_nd; 15115885Sjulian } 15225791Sjulian 15328270Swollman _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 15425791Sjulian const size_type new_checked_ind = 15525791Sjulian static_cast<internal_node_pointer>(p_nd)->get_e_ind(); 15625791Sjulian 15725791Sjulian p_nd = 15825791Sjulian static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); 15925791Sjulian checked_ind = new_checked_ind; 16025791Sjulian } 16125791Sjulian} 16225791Sjulian 16325791SjulianPB_DS_CLASS_T_DEC 16415885Sjulianinline typename PB_DS_CLASS_C_DEC::point_iterator 16525791SjulianPB_DS_CLASS_C_DEC:: 16625791Sjulianlower_bound(const_key_reference r_key) 16725791Sjulian{ return point_iterator(lower_bound_imp(r_key)); } 16825791Sjulian 16915885SjulianPB_DS_CLASS_T_DEC 17025791Sjulianinline typename PB_DS_CLASS_C_DEC::const_point_iterator 17125791SjulianPB_DS_CLASS_C_DEC:: 17225791Sjulianlower_bound(const_key_reference r_key) const 17315885Sjulian{ 17425791Sjulian return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key)); 17528270Swollman} 17615885Sjulian 17725791SjulianPB_DS_CLASS_T_DEC 17825791Sjulianinline typename PB_DS_CLASS_C_DEC::point_iterator 17925791SjulianPB_DS_CLASS_C_DEC:: 18015885Sjulianupper_bound(const_key_reference r_key) 18125791Sjulian{ 18225791Sjulian point_iterator l_bound_it = lower_bound(r_key); 18325791Sjulian 18415885Sjulian _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 18515885Sjulian !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 18625791Sjulian r_key)); 18723396Sjulian 18815885Sjulian if (l_bound_it == end() || 18915885Sjulian synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 19015885Sjulian return l_bound_it; 19125791Sjulian 19225791Sjulian return ++l_bound_it; 19325791Sjulian} 19425791Sjulian 19525791SjulianPB_DS_CLASS_T_DEC 19625791Sjulianinline typename PB_DS_CLASS_C_DEC::const_point_iterator 19725791SjulianPB_DS_CLASS_C_DEC:: 19825791Sjulianupper_bound(const_key_reference r_key) const 19925791Sjulian{ 20025791Sjulian const_point_iterator l_bound_it = lower_bound(r_key); 20125791Sjulian 20225791Sjulian _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || 20325791Sjulian !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), 20415885Sjulian r_key)); 20515885Sjulian 20625791Sjulian if (l_bound_it == end() || 20715885Sjulian synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) 20825791Sjulian return l_bound_it; 20925791Sjulian return ++l_bound_it; 21025791Sjulian} 21115885Sjulian 21215885SjulianPB_DS_CLASS_T_DEC 21315885Sjulianinline typename PB_DS_CLASS_C_DEC::const_e_iterator 21428270SwollmanPB_DS_CLASS_C_DEC:: 21515885Sjulianpref_begin(const_node_pointer p_nd) 21628270Swollman{ 21715885Sjulian if (p_nd->m_type == pat_trie_leaf_node_type) 21815885Sjulian return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); 21915885Sjulian 22028270Swollman _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 22115885Sjulian return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it(); 22215885Sjulian} 22315885Sjulian 22415885SjulianPB_DS_CLASS_T_DEC 22515885Sjulianinline typename PB_DS_CLASS_C_DEC::const_e_iterator 22615885SjulianPB_DS_CLASS_C_DEC:: 22715885Sjulianpref_end(const_node_pointer p_nd) 22815885Sjulian{ 22915885Sjulian if (p_nd->m_type == pat_trie_leaf_node_type) 23028270Swollman return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); 23128270Swollman 23228270Swollman _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 23328270Swollman return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it(); 23415885Sjulian} 23515885Sjulian 23615885SjulianPB_DS_CLASS_T_DEC 23715885Sjulianinline typename PB_DS_CLASS_C_DEC::const_leaf_pointer 23815885SjulianPB_DS_CLASS_C_DEC:: 23915885Sjulianleftmost_descendant(const_node_pointer p_nd) 24015885Sjulian{ 24115885Sjulian if (p_nd->m_type == pat_trie_leaf_node_type) 24215885Sjulian return static_cast<const_leaf_pointer>(p_nd); 24315885Sjulian return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant(); 24415885Sjulian} 24515885Sjulian 24615885SjulianPB_DS_CLASS_T_DEC 24715885Sjulianinline typename PB_DS_CLASS_C_DEC::leaf_pointer 24815885SjulianPB_DS_CLASS_C_DEC:: 24915885Sjulianleftmost_descendant(node_pointer p_nd) 25015885Sjulian{ 25115885Sjulian if (p_nd->m_type == pat_trie_leaf_node_type) 25215885Sjulian return static_cast<leaf_pointer>(p_nd); 25315885Sjulian return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); 25415885Sjulian} 25517254Sjulian 25615885SjulianPB_DS_CLASS_T_DEC 25715885Sjulianinline typename PB_DS_CLASS_C_DEC::const_leaf_pointer 25815885SjulianPB_DS_CLASS_C_DEC:: 25915885Sjulianrightmost_descendant(const_node_pointer p_nd) 26015885Sjulian{ 26115885Sjulian if (p_nd->m_type == pat_trie_leaf_node_type) 26215885Sjulian return static_cast<const_leaf_pointer>(p_nd); 26315885Sjulian return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant(); 26415885Sjulian} 26515885Sjulian 26615885SjulianPB_DS_CLASS_T_DEC 26715885Sjulianinline typename PB_DS_CLASS_C_DEC::leaf_pointer 26815885SjulianPB_DS_CLASS_C_DEC:: 26915885Sjulianrightmost_descendant(node_pointer p_nd) 27015885Sjulian{ 27115885Sjulian if (p_nd->m_type == pat_trie_leaf_node_type) 27215885Sjulian return static_cast<leaf_pointer>(p_nd); 27315885Sjulian return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); 27415885Sjulian} 27515885Sjulian 27615885Sjulian