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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2011 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file pat_trie_/synth_access_traits.hpp
  38  * Contains an implementation class for a patricia tree.
  39  */
  40
  41 #ifndef PB_DS_SYNTH_E_ACCESS_TRAITS_HPP
  42 #define PB_DS_SYNTH_E_ACCESS_TRAITS_HPP
  43
  44 #include <ext/pb_ds/detail/type_utils.hpp>
  45
  46 namespace __gnu_pbds
  47 {
  48   namespace detail
  49   {
  50
  51 #define PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC \
  52     template<typename Type_Traits, bool Set, typename _ATraits>
  53
  54 #define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \
  55     synth_access_traits<Type_Traits, Set, _ATraits>
  56
  57     /// Synthetic element access traits.
  58     template<typename Type_Traits, bool Set, typename _ATraits>
  59     struct synth_access_traits : public _ATraits
  60     {
  61       typedef _ATraits                                  base_type;
  62       typedef typename base_type::const_iterator        const_iterator;
  63       typedef Type_Traits                               type_traits;
  64       typedef typename type_traits::const_reference     const_reference;
  65       typedef typename type_traits::key_const_reference key_const_reference;
  66
  67       synth_access_traits();
  68
  69       synth_access_traits(const base_type&);
  70
  71       inline bool
  72       equal_prefixes(const_iterator, const_iterator, const_iterator,
  73                      const_iterator, bool compare_after = true) const;
  74
  75       bool
  76       equal_keys(key_const_reference, key_const_reference) const;
  77
  78       bool
  79       cmp_prefixes(const_iterator, const_iterator, const_iterator,
  80                    const_iterator, bool compare_after = false) const;
  81
  82       bool
  83       cmp_keys(key_const_reference, key_const_reference) const;
  84
  85       inline static key_const_reference
  86       extract_key(const_reference);
  87
  88 #ifdef _GLIBCXX_DEBUG
  89       bool
  90       operator()(key_const_reference, key_const_reference);
  91 #endif
  92
  93     private:
  94       inline static key_const_reference
  95       extract_key(const_reference, true_type);
  96
  97       inline static key_const_reference
  98       extract_key(const_reference, false_type);
  99
 100       static integral_constant<int, Set> s_set_ind;
 101     };
 102
 103     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 104     integral_constant<int,Set>
 105     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::s_set_ind;
 106
 107     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 108     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 109     synth_access_traits()
 110     { }
 111
 112     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 113     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 114     synth_access_traits(const _ATraits& r_traits)
 115     : _ATraits(r_traits)
 116     { }
 117
 118     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 119     inline bool
 120     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 121     equal_prefixes(const_iterator b_l, const_iterator e_l, const_iterator b_r,
 122                    const_iterator e_r, bool compare_after /*= false */) const
 123     {
 124       while (b_l != e_l)
 125         {
 126           if (b_r == e_r)
 127             return false;
 128           if (base_type::e_pos(*b_l) != base_type::e_pos(*b_r))
 129             return false;
 130           ++b_l;
 131           ++b_r;
 132         }
 133       return (!compare_after || b_r == e_r);
 134     }
 135
 136     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 137     bool
 138     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 139     equal_keys(key_const_reference r_lhs_key,
 140                key_const_reference r_rhs_key) const
 141     {
 142       return equal_prefixes(base_type::begin(r_lhs_key),
 143                             base_type::end(r_lhs_key),
 144                             base_type::begin(r_rhs_key),
 145                             base_type::end(r_rhs_key),
 146                             true);
 147     }
 148
 149     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 150     bool
 151     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 152     cmp_prefixes(const_iterator b_l, const_iterator e_l, const_iterator b_r,
 153                  const_iterator e_r, bool compare_after /* = false*/) const
 154     {
 155       while (b_l != e_l)
 156         {
 157           if (b_r == e_r)
 158             return false;
 159
 160           const typename base_type::size_type l_pos = base_type::e_pos(*b_l);
 161           const typename base_type::size_type r_pos = base_type::e_pos(*b_r);
 162           if (l_pos != r_pos)
 163             return l_pos < r_pos;
 164           ++b_l;
 165           ++b_r;
 166         }
 167
 168       if (!compare_after)
 169         return false;
 170       return b_r != e_r;
 171     }
 172
 173     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 174     bool
 175     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 176     cmp_keys(key_const_reference r_lhs_key,
 177              key_const_reference r_rhs_key) const
 178     {
 179       return cmp_prefixes(base_type::begin(r_lhs_key),
 180                           base_type::end(r_lhs_key),
 181                           base_type::begin(r_rhs_key),
 182                           base_type::end(r_rhs_key),
 183                           true);
 184     }
 185
 186     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 187     inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::key_const_reference
 188     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 189     extract_key(const_reference r_val)
 190     { return extract_key(r_val, s_set_ind); }
 191
 192     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 193     inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::key_const_reference
 194     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 195     extract_key(const_reference r_val, true_type)
 196     { return r_val; }
 197
 198     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 199     inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::key_const_reference
 200     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 201     extract_key(const_reference r_val, false_type)
 202     { return r_val.first; }
 203
 204 #ifdef _GLIBCXX_DEBUG
 205     PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 206     bool
 207     PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
 208     operator()(key_const_reference r_lhs, key_const_reference r_rhs)
 209     { return cmp_keys(r_lhs, r_rhs); }
 210 #endif
 211
 212 #undef PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
 213 #undef PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC
 214
 215   } // namespace detail
 216 } // namespace __gnu_pbds
 217
 218 #endif