1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// 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 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file synth_e_access_traits.hpp 44169691Skan * Contains an implementation class for a patricia tree. 45169691Skan */ 46169691Skan 47169691Skan#ifndef PB_DS_SYNTH_E_ACCESS_TRAITS_HPP 48169691Skan#define PB_DS_SYNTH_E_ACCESS_TRAITS_HPP 49169691Skan 50169691Skan#include <ext/pb_ds/detail/type_utils.hpp> 51169691Skan 52169691Skannamespace pb_ds 53169691Skan{ 54169691Skan namespace detail 55169691Skan { 56169691Skan 57169691Skan#define PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC \ 58169691Skan template<typename Type_Traits, bool Set, class E_Access_Traits> 59169691Skan 60169691Skan#define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \ 61169691Skan synth_e_access_traits< \ 62169691Skan Type_Traits, \ 63169691Skan Set, \ 64169691Skan E_Access_Traits> 65169691Skan 66169691Skan template<typename Type_Traits, bool Set, class E_Access_Traits> 67169691Skan struct synth_e_access_traits : public E_Access_Traits 68169691Skan { 69169691Skan 70169691Skan private: 71169691Skan typedef E_Access_Traits base_type; 72169691Skan 73169691Skan typedef Type_Traits type_traits; 74169691Skan 75169691Skan typedef typename type_traits::const_key_reference const_key_reference; 76169691Skan 77169691Skan typedef typename type_traits::const_reference const_reference; 78169691Skan 79169691Skan public: 80169691Skan synth_e_access_traits(); 81169691Skan 82169691Skan synth_e_access_traits(const E_Access_Traits& r_traits); 83169691Skan 84169691Skan inline bool 85169691Skan 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; 86169691Skan 87169691Skan bool 88169691Skan equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; 89169691Skan 90169691Skan bool 91169691Skan 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; 92169691Skan 93169691Skan bool 94169691Skan cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; 95169691Skan 96169691Skan inline static const_key_reference 97169691Skan extract_key(const_reference r_val); 98169691Skan 99169691Skan#ifdef _GLIBCXX_DEBUG 100169691Skan bool 101169691Skan operator()(const_key_reference r_lhs, const_key_reference r_rhs); 102169691Skan#endif 103169691Skan 104169691Skan private: 105169691Skan inline static const_key_reference 106169691Skan extract_key(const_reference r_val, true_type); 107169691Skan 108169691Skan inline static const_key_reference 109169691Skan extract_key(const_reference r_val, false_type); 110169691Skan 111169691Skan private: 112169691Skan static integral_constant<int,Set> s_set_ind; 113169691Skan }; 114169691Skan 115169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 116169691Skan integral_constant<int,Set> 117169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::s_set_ind; 118169691Skan 119169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 120169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 121169691Skan synth_e_access_traits() 122169691Skan { } 123169691Skan 124169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 125169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 126169691Skan synth_e_access_traits(const E_Access_Traits& r_traits) : 127169691Skan E_Access_Traits(r_traits) 128169691Skan { } 129169691Skan 130169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 131169691Skan inline bool 132169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 133169691Skan 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 134169691Skan { 135169691Skan while (b_l != e_l) 136169691Skan { 137169691Skan if (b_r == e_r) 138169691Skan return (false); 139169691Skan if (base_type::e_pos(*b_l) != base_type::e_pos(*b_r)) 140169691Skan return (false); 141169691Skan ++b_l; 142169691Skan ++b_r; 143169691Skan } 144169691Skan return (!compare_after || b_r == e_r); 145169691Skan } 146169691Skan 147169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 148169691Skan bool 149169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 150169691Skan equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const 151169691Skan { 152169691Skan return (equal_prefixes(base_type::begin(r_lhs_key), 153169691Skan base_type::end(r_lhs_key), 154169691Skan base_type::begin(r_rhs_key), 155169691Skan base_type::end(r_rhs_key), 156169691Skan true)); 157169691Skan } 158169691Skan 159169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 160169691Skan bool 161169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 162169691Skan 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 163169691Skan { 164169691Skan while (b_l != e_l) 165169691Skan { 166169691Skan if (b_r == e_r) 167169691Skan return (false); 168169691Skan const typename base_type::size_type l_pos = 169169691Skan base_type::e_pos(*b_l); 170169691Skan const typename base_type::size_type r_pos = 171169691Skan base_type::e_pos(*b_r); 172169691Skan if (l_pos != r_pos) 173169691Skan return (l_pos < r_pos); 174169691Skan ++b_l; 175169691Skan ++b_r; 176169691Skan } 177169691Skan 178169691Skan if (!compare_after) 179169691Skan return (false); 180169691Skan return (b_r != e_r); 181169691Skan } 182169691Skan 183169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 184169691Skan bool 185169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 186169691Skan cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const 187169691Skan { 188169691Skan return (cmp_prefixes(base_type::begin(r_lhs_key), 189169691Skan base_type::end(r_lhs_key), 190169691Skan base_type::begin(r_rhs_key), 191169691Skan base_type::end(r_rhs_key), 192169691Skan true)); 193169691Skan } 194169691Skan 195169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 196169691Skan inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference 197169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 198169691Skan extract_key(const_reference r_val) 199169691Skan { 200169691Skan return (extract_key(r_val, s_set_ind)); 201169691Skan } 202169691Skan 203169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 204169691Skan inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference 205169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 206169691Skan extract_key(const_reference r_val, true_type) 207169691Skan { 208169691Skan return (r_val); 209169691Skan } 210169691Skan 211169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 212169691Skan inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference 213169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 214169691Skan extract_key(const_reference r_val, false_type) 215169691Skan { 216169691Skan return (r_val.first); 217169691Skan } 218169691Skan 219169691Skan#ifdef _GLIBCXX_DEBUG 220169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 221169691Skan bool 222169691Skan PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 223169691Skan operator()(const_key_reference r_lhs, const_key_reference r_rhs) 224169691Skan { 225169691Skan return (cmp_keys(r_lhs, r_rhs)); 226169691Skan } 227169691Skan#endif 228169691Skan 229169691Skan#undef PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 230169691Skan#undef PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC 231169691Skan 232169691Skan } // namespace detail 233169691Skan} // namespace pb_ds 234169691Skan 235169691Skan#endif 236