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 prefix_search_node_update_imp.hpp 44169691Skan * Contains an implementation of prefix_search_node_update. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skanstd::pair< 49169691Skan typename PB_DS_CLASS_C_DEC::const_iterator, 50169691Skan typename PB_DS_CLASS_C_DEC::const_iterator> 51169691SkanPB_DS_CLASS_C_DEC:: 52169691Skanprefix_range(const_key_reference r_key) const 53169691Skan{ 54169691Skan const e_access_traits& r_traits = get_e_access_traits(); 55169691Skan 56169691Skan return (prefix_range( 57169691Skan r_traits.begin(r_key), 58169691Skan r_traits.end(r_key))); 59169691Skan} 60169691Skan 61169691SkanPB_DS_CLASS_T_DEC 62169691Skanstd::pair< 63169691Skan typename PB_DS_CLASS_C_DEC::iterator, 64169691Skan typename PB_DS_CLASS_C_DEC::iterator> 65169691SkanPB_DS_CLASS_C_DEC:: 66169691Skanprefix_range(const_key_reference r_key) 67169691Skan{ 68169691Skan return (prefix_range( 69169691Skan get_e_access_traits().begin(r_key), 70169691Skan get_e_access_traits().end(r_key))); 71169691Skan} 72169691Skan 73169691SkanPB_DS_CLASS_T_DEC 74169691Skanstd::pair< 75169691Skan typename PB_DS_CLASS_C_DEC::const_iterator, 76169691Skan typename PB_DS_CLASS_C_DEC::const_iterator> 77169691SkanPB_DS_CLASS_C_DEC:: 78169691Skanprefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) const 79169691Skan{ 80169691Skan const std::pair<iterator, iterator> non_const_ret = 81169691Skan const_cast<PB_DS_CLASS_C_DEC* >(this)->prefix_range(b, e); 82169691Skan 83169691Skan return (std::make_pair( 84169691Skan const_iterator(non_const_ret.first), 85169691Skan const_iterator(non_const_ret.second))); 86169691Skan} 87169691Skan 88169691SkanPB_DS_CLASS_T_DEC 89169691Skanstd::pair< 90169691Skan typename PB_DS_CLASS_C_DEC::iterator, 91169691Skan typename PB_DS_CLASS_C_DEC::iterator> 92169691SkanPB_DS_CLASS_C_DEC:: 93169691Skanprefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) 94169691Skan{ 95169691Skan Node_Iterator nd_it = node_begin(); 96169691Skan Node_Iterator end_nd_it = node_end(); 97169691Skan 98169691Skan const e_access_traits& r_traits = 99169691Skan get_e_access_traits(); 100169691Skan 101169691Skan const size_type given_range_length = std::distance(b, e); 102169691Skan 103169691Skan while (true) 104169691Skan { 105169691Skan if (nd_it == end_nd_it) 106169691Skan return (std::make_pair(end(), end())); 107169691Skan 108169691Skan const size_type common_range_length = 109169691Skan PB_DS_BASE_C_DEC::common_prefix_len(nd_it, b, e, r_traits); 110169691Skan 111169691Skan if (common_range_length >= given_range_length) 112169691Skan { 113169691Skan iterator ret_b = leftmost_it(nd_it); 114169691Skan 115169691Skan iterator ret_e = rightmost_it(nd_it); 116169691Skan 117169691Skan return (std::make_pair(ret_b, ++ret_e)); 118169691Skan } 119169691Skan 120169691Skan nd_it = next_child(nd_it, b, e, end_nd_it, r_traits); 121169691Skan } 122169691Skan} 123169691Skan 124169691SkanPB_DS_CLASS_T_DEC 125169691Skantypename PB_DS_CLASS_C_DEC::node_iterator 126169691SkanPB_DS_CLASS_C_DEC:: 127169691Skannext_child(node_iterator nd_it, typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e, node_iterator end_nd_it, const e_access_traits& r_traits) 128169691Skan{ 129169691Skan const size_type num_children = nd_it.num_children(); 130169691Skan 131169691Skan node_iterator ret = end_nd_it; 132169691Skan 133169691Skan size_type max_length = 0; 134169691Skan 135169691Skan for (size_type i = 0; i < num_children; ++i) 136169691Skan { 137169691Skan node_iterator pot = nd_it.get_child(i); 138169691Skan 139169691Skan const size_type common_range_length = 140169691Skan PB_DS_BASE_C_DEC::common_prefix_len( pot, b, e, r_traits); 141169691Skan 142169691Skan if (common_range_length > max_length) 143169691Skan { 144169691Skan ret = pot; 145169691Skan 146169691Skan max_length = common_range_length; 147169691Skan } 148169691Skan } 149169691Skan 150169691Skan return (ret); 151169691Skan} 152169691Skan 153169691SkanPB_DS_CLASS_T_DEC 154169691Skaninline void 155169691SkanPB_DS_CLASS_C_DEC:: 156169691Skanoperator()(node_iterator /*nd_it*/, const_node_iterator /*end_nd_it*/) const 157169691Skan{ } 158