synth_e_access_traits.hpp revision 256281
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 52namespace 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:: 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:: 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:: 133 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:: 150 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:: 162 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:: 186 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:: 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:: 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:: 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:: 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