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 synth_e_access_traits.hpp 44 * Contains an implementation class for a patricia tree. 45 */ 46 47 #ifndef PB_DS_SYNTH_E_ACCESS_TRAITS_HPP 48 #define PB_DS_SYNTH_E_ACCESS_TRAITS_HPP 49 50 #include <ext/pb_ds/detail/type_utils.hpp> 51 52 namespace pb_ds 53 { 54 namespace detail 55 { 56 57 #define PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC \ 58 template<typename Type_Traits, bool Set, class E_Access_Traits> 59 60 #define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \ 61 synth_e_access_traits< \ 62 Type_Traits, \ 63 Set, \ 64 E_Access_Traits> 65 66 template<typename Type_Traits, bool Set, class E_Access_Traits> 67 struct synth_e_access_traits : public E_Access_Traits 68 { 69 70 private: 71 typedef E_Access_Traits base_type; 72 73 typedef Type_Traits type_traits; 74 75 typedef typename type_traits::const_key_reference const_key_reference; 76 77 typedef typename type_traits::const_reference const_reference; 78 79 public: 80 synth_e_access_traits(); 81 82 synth_e_access_traits(const E_Access_Traits& r_traits); 83 84 inline bool 85 equal_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after = true) const; 86 87 bool 88 equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; 89 90 bool 91 cmp_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after = false) const; 92 93 bool 94 cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; 95 96 inline static const_key_reference 97 extract_key(const_reference r_val); 98 99 #ifdef _GLIBCXX_DEBUG 100 bool 101 operator()(const_key_reference r_lhs, const_key_reference r_rhs); 102 #endif 103 104 private: 105 inline static const_key_reference 106 extract_key(const_reference r_val, true_type); 107 108 inline static const_key_reference 109 extract_key(const_reference r_val, false_type); 110 111 private: 112 static integral_constant<int,Set> s_set_ind; 113 }; 114 115 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 116 integral_constant<int,Set> 117 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::s_set_ind; 118 119 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 120 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: synth_e_access_traits()121 synth_e_access_traits() 122 { } 123 124 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 125 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: synth_e_access_traits(const E_Access_Traits & r_traits)126 synth_e_access_traits(const E_Access_Traits& r_traits) : 127 E_Access_Traits(r_traits) 128 { } 129 130 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 131 inline bool 132 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: equal_prefixes(typename base_type::const_iterator b_l,typename base_type::const_iterator e_l,typename base_type::const_iterator b_r,typename base_type::const_iterator e_r,bool compare_after) const133 equal_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after /*= false */) const 134 { 135 while (b_l != e_l) 136 { 137 if (b_r == e_r) 138 return (false); 139 if (base_type::e_pos(*b_l) != base_type::e_pos(*b_r)) 140 return (false); 141 ++b_l; 142 ++b_r; 143 } 144 return (!compare_after || b_r == e_r); 145 } 146 147 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 148 bool 149 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: equal_keys(const_key_reference r_lhs_key,const_key_reference r_rhs_key) const150 equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const 151 { 152 return (equal_prefixes(base_type::begin(r_lhs_key), 153 base_type::end(r_lhs_key), 154 base_type::begin(r_rhs_key), 155 base_type::end(r_rhs_key), 156 true)); 157 } 158 159 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 160 bool 161 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: cmp_prefixes(typename base_type::const_iterator b_l,typename base_type::const_iterator e_l,typename base_type::const_iterator b_r,typename base_type::const_iterator e_r,bool compare_after) const162 cmp_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after /* = false*/) const 163 { 164 while (b_l != e_l) 165 { 166 if (b_r == e_r) 167 return (false); 168 const typename base_type::size_type l_pos = 169 base_type::e_pos(*b_l); 170 const typename base_type::size_type r_pos = 171 base_type::e_pos(*b_r); 172 if (l_pos != r_pos) 173 return (l_pos < r_pos); 174 ++b_l; 175 ++b_r; 176 } 177 178 if (!compare_after) 179 return (false); 180 return (b_r != e_r); 181 } 182 183 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 184 bool 185 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: cmp_keys(const_key_reference r_lhs_key,const_key_reference r_rhs_key) const186 cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const 187 { 188 return (cmp_prefixes(base_type::begin(r_lhs_key), 189 base_type::end(r_lhs_key), 190 base_type::begin(r_rhs_key), 191 base_type::end(r_rhs_key), 192 true)); 193 } 194 195 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 196 inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference 197 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: extract_key(const_reference r_val)198 extract_key(const_reference r_val) 199 { 200 return (extract_key(r_val, s_set_ind)); 201 } 202 203 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 204 inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference 205 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: extract_key(const_reference r_val,true_type)206 extract_key(const_reference r_val, true_type) 207 { 208 return (r_val); 209 } 210 211 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 212 inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference 213 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: extract_key(const_reference r_val,false_type)214 extract_key(const_reference r_val, false_type) 215 { 216 return (r_val.first); 217 } 218 219 #ifdef _GLIBCXX_DEBUG 220 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 221 bool 222 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: operator ()(const_key_reference r_lhs,const_key_reference r_rhs)223 operator()(const_key_reference r_lhs, const_key_reference r_rhs) 224 { 225 return (cmp_keys(r_lhs, r_rhs)); 226 } 227 #endif 228 229 #undef PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 230 #undef PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC 231 232 } // namespace detail 233 } // namespace pb_ds 234 235 #endif 236