prefix_search_node_update_imp.hpp revision 256281
197403Sobrien// -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the terms 797403Sobrien// of the GNU General Public License as published by the Free Software 897403Sobrien// Foundation; either version 2, or (at your option) any later 997403Sobrien// version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, but 1297403Sobrien// WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1497403Sobrien// General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License 1797403Sobrien// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1997403Sobrien// MA 02111-1307, USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free 2297403Sobrien// software library without restriction. Specifically, if other files 2397403Sobrien// instantiate templates or use macros or inline functions from this 2497403Sobrien// file, or you compile this file and link it with other files to 2597403Sobrien// produce an executable, this file does not by itself cause the 2697403Sobrien// resulting executable to be covered by the GNU General Public 2797403Sobrien// License. This exception does not however invalidate any other 2897403Sobrien// reasons why the executable file might be covered by the GNU General 2997403Sobrien// 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 3597403Sobrien// notice appears in all copies, and that both that copyright notice 3697403Sobrien// and this permission notice appear in supporting documentation. None 3797403Sobrien// of the above authors, nor IBM Haifa Research Laboratories, make any 3897403Sobrien// representation about the suitability of this software for any 3997403Sobrien// purpose. It is provided "as is" without express or implied 4097403Sobrien// warranty. 4197403Sobrien 4297403Sobrien/** 4397403Sobrien * @file prefix_search_node_update_imp.hpp 4497403Sobrien * Contains an implementation of prefix_search_node_update. 4597403Sobrien */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 4897403Sobrienstd::pair< 49169691Skan typename PB_DS_CLASS_C_DEC::const_iterator, 50169691Skan typename PB_DS_CLASS_C_DEC::const_iterator> 51169691SkanPB_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