Install gcc-4.3.3-tdm-1-g++.tar.gz
[msysgit.git] / mingw / lib / gcc / mingw32 / 4.3.3 / include / c++ / ext / pb_ds / detail / pat_trie_ / synth_e_access_traits.hpp
blob46e8ffa95523cb4298aef981a625b4ae428afb42
1 // -*- C++ -*-
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.
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.
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.
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.
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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.
42 /**
43 * @file synth_e_access_traits.hpp
44 * Contains an implementation class for a patricia tree.
47 #ifndef PB_DS_SYNTH_E_ACCESS_TRAITS_HPP
48 #define PB_DS_SYNTH_E_ACCESS_TRAITS_HPP
50 #include <ext/pb_ds/detail/type_utils.hpp>
52 namespace __gnu_pbds
54 namespace detail
57 #define PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC \
58 template<typename Type_Traits, bool Set, class E_Access_Traits>
60 #define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \
61 synth_e_access_traits< \
62 Type_Traits, \
63 Set, \
64 E_Access_Traits>
66 template<typename Type_Traits, bool Set, class E_Access_Traits>
67 struct synth_e_access_traits : public E_Access_Traits
70 private:
71 typedef E_Access_Traits base_type;
73 typedef Type_Traits type_traits;
75 typedef typename type_traits::const_key_reference const_key_reference;
77 typedef typename type_traits::const_reference const_reference;
79 public:
80 synth_e_access_traits();
82 synth_e_access_traits(const E_Access_Traits& r_traits);
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;
87 bool
88 equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const;
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;
93 bool
94 cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const;
96 inline static const_key_reference
97 extract_key(const_reference r_val);
99 #ifdef _GLIBCXX_DEBUG
100 bool
101 operator()(const_key_reference r_lhs, const_key_reference r_rhs);
102 #endif
104 private:
105 inline static const_key_reference
106 extract_key(const_reference r_val, true_type);
108 inline static const_key_reference
109 extract_key(const_reference r_val, false_type);
111 private:
112 static integral_constant<int,Set> s_set_ind;
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;
119 PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
120 PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::
121 synth_e_access_traits()
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)
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
135 while (b_l != e_l)
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;
144 return (!compare_after || b_r == e_r);
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
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));
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
164 while (b_l != e_l)
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;
178 if (!compare_after)
179 return (false);
180 return (b_r != e_r);
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
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));
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)
200 return (extract_key(r_val, s_set_ind));
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)
208 return (r_val);
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)
216 return (r_val.first);
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)
225 return (cmp_keys(r_lhs, r_rhs));
227 #endif
229 #undef PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC
230 #undef PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC
232 } // namespace detail
233 } // namespace __gnu_pbds
235 #endif