prefix_search_node_update_imp.hpp revision 169691
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 prefix_search_node_update_imp.hpp 44 * Contains an implementation of prefix_search_node_update. 45 */ 46 47PB_DS_CLASS_T_DEC 48std::pair< 49 typename PB_DS_CLASS_C_DEC::const_iterator, 50 typename PB_DS_CLASS_C_DEC::const_iterator> 51PB_DS_CLASS_C_DEC:: 52prefix_range(const_key_reference r_key) const 53{ 54 const e_access_traits& r_traits = get_e_access_traits(); 55 56 return (prefix_range( 57 r_traits.begin(r_key), 58 r_traits.end(r_key))); 59} 60 61PB_DS_CLASS_T_DEC 62std::pair< 63 typename PB_DS_CLASS_C_DEC::iterator, 64 typename PB_DS_CLASS_C_DEC::iterator> 65PB_DS_CLASS_C_DEC:: 66prefix_range(const_key_reference r_key) 67{ 68 return (prefix_range( 69 get_e_access_traits().begin(r_key), 70 get_e_access_traits().end(r_key))); 71} 72 73PB_DS_CLASS_T_DEC 74std::pair< 75 typename PB_DS_CLASS_C_DEC::const_iterator, 76 typename PB_DS_CLASS_C_DEC::const_iterator> 77PB_DS_CLASS_C_DEC:: 78prefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) const 79{ 80 const std::pair<iterator, iterator> non_const_ret = 81 const_cast<PB_DS_CLASS_C_DEC* >(this)->prefix_range(b, e); 82 83 return (std::make_pair( 84 const_iterator(non_const_ret.first), 85 const_iterator(non_const_ret.second))); 86} 87 88PB_DS_CLASS_T_DEC 89std::pair< 90 typename PB_DS_CLASS_C_DEC::iterator, 91 typename PB_DS_CLASS_C_DEC::iterator> 92PB_DS_CLASS_C_DEC:: 93prefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) 94{ 95 Node_Iterator nd_it = node_begin(); 96 Node_Iterator end_nd_it = node_end(); 97 98 const e_access_traits& r_traits = 99 get_e_access_traits(); 100 101 const size_type given_range_length = std::distance(b, e); 102 103 while (true) 104 { 105 if (nd_it == end_nd_it) 106 return (std::make_pair(end(), end())); 107 108 const size_type common_range_length = 109 PB_DS_BASE_C_DEC::common_prefix_len(nd_it, b, e, r_traits); 110 111 if (common_range_length >= given_range_length) 112 { 113 iterator ret_b = leftmost_it(nd_it); 114 115 iterator ret_e = rightmost_it(nd_it); 116 117 return (std::make_pair(ret_b, ++ret_e)); 118 } 119 120 nd_it = next_child(nd_it, b, e, end_nd_it, r_traits); 121 } 122} 123 124PB_DS_CLASS_T_DEC 125typename PB_DS_CLASS_C_DEC::node_iterator 126PB_DS_CLASS_C_DEC:: 127next_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) 128{ 129 const size_type num_children = nd_it.num_children(); 130 131 node_iterator ret = end_nd_it; 132 133 size_type max_length = 0; 134 135 for (size_type i = 0; i < num_children; ++i) 136 { 137 node_iterator pot = nd_it.get_child(i); 138 139 const size_type common_range_length = 140 PB_DS_BASE_C_DEC::common_prefix_len( pot, b, e, r_traits); 141 142 if (common_range_length > max_length) 143 { 144 ret = pot; 145 146 max_length = common_range_length; 147 } 148 } 149 150 return (ret); 151} 152 153PB_DS_CLASS_T_DEC 154inline void 155PB_DS_CLASS_C_DEC:: 156operator()(node_iterator /*nd_it*/, const_node_iterator /*end_nd_it*/) const 157{ } 158