libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp

   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 __gnu_pbds
  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 __gnu_pbds
 234
 235 #endif