prefix_search_node_update_imp.hpp revision 169691
1296417Sdim// -*- C++ -*- 2275072Semaste 3275072Semaste// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4275072Semaste// 5275072Semaste// This file is part of the GNU ISO C++ Library. This library is free 6275072Semaste// software; you can redistribute it and/or modify it under the terms 7275072Semaste// of the GNU General Public License as published by the Free Software 8275072Semaste// Foundation; either version 2, or (at your option) any later 9275072Semaste// version. 10275072Semaste 11275072Semaste// This library is distributed in the hope that it will be useful, but 12275072Semaste// WITHOUT ANY WARRANTY; without even the implied warranty of 13275072Semaste// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14275072Semaste// General Public License for more details. 15280031Sdim 16275072Semaste// You should have received a copy of the GNU General Public License 17275072Semaste// along with this library; see the file COPYING. If not, write to 18280031Sdim// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19280031Sdim// MA 02111-1307, USA. 20280031Sdim 21280031Sdim// As a special exception, you may use this file as part of a free 22280031Sdim// software library without restriction. Specifically, if other files 23275072Semaste// instantiate templates or use macros or inline functions from this 24296417Sdim// file, or you compile this file and link it with other files to 25280031Sdim// produce an executable, this file does not by itself cause the 26275072Semaste// resulting executable to be covered by the GNU General Public 27275072Semaste// License. This exception does not however invalidate any other 28275072Semaste// reasons why the executable file might be covered by the GNU General 29275072Semaste// Public License. 30280031Sdim 31280031Sdim// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32280031Sdim 33280031Sdim// Permission to use, copy, modify, sell, and distribute this software 34280031Sdim// is hereby granted without fee, provided that the above copyright 35280031Sdim// notice appears in all copies, and that both that copyright notice 36275072Semaste// and this permission notice appear in supporting documentation. None 37280031Sdim// of the above authors, nor IBM Haifa Research Laboratories, make any 38280031Sdim// representation about the suitability of this software for any 39280031Sdim// purpose. It is provided "as is" without express or implied 40280031Sdim// warranty. 41280031Sdim 42275072Semaste/** 43280031Sdim * @file prefix_search_node_update_imp.hpp 44275072Semaste * Contains an implementation of prefix_search_node_update. 45275072Semaste */ 46275072Semaste 47280031SdimPB_DS_CLASS_T_DEC 48280031Sdimstd::pair< 49280031Sdim typename PB_DS_CLASS_C_DEC::const_iterator, 50280031Sdim typename PB_DS_CLASS_C_DEC::const_iterator> 51288943SdimPB_DS_CLASS_C_DEC:: 52280031Sdimprefix_range(const_key_reference r_key) const 53280031Sdim{ 54275072Semaste const e_access_traits& r_traits = get_e_access_traits(); 55280031Sdim 56280031Sdim return (prefix_range( 57280031Sdim r_traits.begin(r_key), 58280031Sdim r_traits.end(r_key))); 59280031Sdim} 60275072Semaste 61280031SdimPB_DS_CLASS_T_DEC 62275072Semastestd::pair< 63275072Semaste typename PB_DS_CLASS_C_DEC::iterator, 64275072Semaste typename PB_DS_CLASS_C_DEC::iterator> 65280031SdimPB_DS_CLASS_C_DEC:: 66280031Sdimprefix_range(const_key_reference r_key) 67280031Sdim{ 68280031Sdim return (prefix_range( 69280031Sdim get_e_access_traits().begin(r_key), 70275072Semaste get_e_access_traits().end(r_key))); 71296417Sdim} 72275072Semaste 73275072SemastePB_DS_CLASS_T_DEC 74275072Semastestd::pair< 75275072Semaste typename PB_DS_CLASS_C_DEC::const_iterator, 76280031Sdim typename PB_DS_CLASS_C_DEC::const_iterator> 77280031SdimPB_DS_CLASS_C_DEC:: 78280031Sdimprefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) const 79296417Sdim{ 80280031Sdim const std::pair<iterator, iterator> non_const_ret = 81275072Semaste const_cast<PB_DS_CLASS_C_DEC* >(this)->prefix_range(b, e); 82296417Sdim 83296417Sdim return (std::make_pair( 84275072Semaste const_iterator(non_const_ret.first), 85288943Sdim const_iterator(non_const_ret.second))); 86280031Sdim} 87275072Semaste 88275072SemastePB_DS_CLASS_T_DEC 89275072Semastestd::pair< 90280031Sdim typename PB_DS_CLASS_C_DEC::iterator, 91280031Sdim typename PB_DS_CLASS_C_DEC::iterator> 92280031SdimPB_DS_CLASS_C_DEC:: 93280031Sdimprefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) 94296417Sdim{ 95280031Sdim Node_Iterator nd_it = node_begin(); 96275072Semaste Node_Iterator end_nd_it = node_end(); 97296417Sdim 98280031Sdim const e_access_traits& r_traits = 99275072Semaste get_e_access_traits(); 100288943Sdim 101280031Sdim const size_type given_range_length = std::distance(b, e); 102280031Sdim 103275072Semaste while (true) 104275072Semaste { 105275072Semaste if (nd_it == end_nd_it) 106280031Sdim return (std::make_pair(end(), end())); 107280031Sdim 108280031Sdim const size_type common_range_length = 109280031Sdim PB_DS_BASE_C_DEC::common_prefix_len(nd_it, b, e, r_traits); 110280031Sdim 111280031Sdim if (common_range_length >= given_range_length) 112280031Sdim { 113275072Semaste iterator ret_b = leftmost_it(nd_it); 114296417Sdim 115280031Sdim iterator ret_e = rightmost_it(nd_it); 116275072Semaste 117280031Sdim return (std::make_pair(ret_b, ++ret_e)); 118296417Sdim } 119280031Sdim 120280031Sdim nd_it = next_child(nd_it, b, e, end_nd_it, r_traits); 121280031Sdim } 122280031Sdim} 123280031Sdim 124296417SdimPB_DS_CLASS_T_DEC 125280031Sdimtypename PB_DS_CLASS_C_DEC::node_iterator 126275072SemastePB_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