00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
00037 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
00038
00039 #include <bits/stl_algobase.h>
00040 #include <parallel/base.h>
00041 #include <parallel/tags.h>
00042 #include <parallel/settings.h>
00043 #include <parallel/find.h>
00044 #include <parallel/find_selectors.h>
00045
00046 namespace std
00047 {
00048 namespace __parallel
00049 {
00050
00051
00052
00053 template<typename InputIterator1, typename InputIterator2>
00054 inline pair<InputIterator1, InputIterator2>
00055 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00056 __gnu_parallel::sequential_tag)
00057 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
00058
00059
00060 template<typename InputIterator1, typename InputIterator2,
00061 typename Predicate>
00062 inline pair<InputIterator1, InputIterator2>
00063 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00064 Predicate pred, __gnu_parallel::sequential_tag)
00065 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
00066
00067
00068 template<typename InputIterator1, typename InputIterator2,
00069 typename Predicate, typename IteratorTag1, typename IteratorTag2>
00070 inline pair<InputIterator1, InputIterator2>
00071 mismatch_switch(InputIterator1 begin1, InputIterator1 end1,
00072 InputIterator2 begin2, Predicate pred, IteratorTag1,
00073 IteratorTag2)
00074 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
00075
00076
00077 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00078 typename Predicate>
00079 pair<RandomAccessIterator1, RandomAccessIterator2>
00080 mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
00081 RandomAccessIterator2 begin2, Predicate pred,
00082 random_access_iterator_tag, random_access_iterator_tag)
00083 {
00084 if (_GLIBCXX_PARALLEL_CONDITION(true))
00085 {
00086 RandomAccessIterator1 res =
00087 __gnu_parallel::find_template(begin1, end1, begin2, pred,
00088 __gnu_parallel::
00089 mismatch_selector()).first;
00090 return make_pair(res , begin2 + (res - begin1));
00091 }
00092 else
00093 return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
00094 }
00095
00096
00097 template<typename InputIterator1, typename InputIterator2>
00098 inline pair<InputIterator1, InputIterator2>
00099 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
00100 {
00101 typedef std::iterator_traits<InputIterator1> iterator1_traits;
00102 typedef std::iterator_traits<InputIterator2> iterator2_traits;
00103 typedef typename iterator1_traits::value_type value1_type;
00104 typedef typename iterator2_traits::value_type value2_type;
00105 typedef typename iterator1_traits::iterator_category iterator1_category;
00106 typedef typename iterator2_traits::iterator_category iterator2_category;
00107
00108 typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type;
00109
00110 return mismatch_switch(begin1, end1, begin2, equal_to_type(),
00111 iterator1_category(), iterator2_category());
00112 }
00113
00114
00115 template<typename InputIterator1, typename InputIterator2,
00116 typename Predicate>
00117 inline pair<InputIterator1, InputIterator2>
00118 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00119 Predicate pred)
00120 {
00121 typedef std::iterator_traits<InputIterator1> iterator1_traits;
00122 typedef std::iterator_traits<InputIterator2> iterator2_traits;
00123 typedef typename iterator1_traits::iterator_category iterator1_category;
00124 typedef typename iterator2_traits::iterator_category iterator2_category;
00125
00126 return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(),
00127 iterator2_category());
00128 }
00129
00130
00131 template<typename InputIterator1, typename InputIterator2>
00132 inline bool
00133 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00134 __gnu_parallel::sequential_tag)
00135 { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
00136
00137
00138 template<typename InputIterator1, typename InputIterator2,
00139 typename Predicate>
00140 inline bool
00141 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00142 Predicate pred, __gnu_parallel::sequential_tag)
00143 { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
00144
00145
00146 template<typename InputIterator1, typename InputIterator2>
00147 inline bool
00148 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
00149 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2).first == end1; }
00150
00151
00152 template<typename InputIterator1, typename InputIterator2,
00153 typename Predicate>
00154 inline bool
00155 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
00156 Predicate pred)
00157 {
00158 return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred).first
00159 == end1;
00160 }
00161
00162
00163 template<typename InputIterator1, typename InputIterator2>
00164 inline bool
00165 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00166 InputIterator2 begin2, InputIterator2 end2,
00167 __gnu_parallel::sequential_tag)
00168 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00169 begin2, end2); }
00170
00171
00172 template<typename InputIterator1, typename InputIterator2,
00173 typename Predicate>
00174 inline bool
00175 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00176 InputIterator2 begin2, InputIterator2 end2,
00177 Predicate pred, __gnu_parallel::sequential_tag)
00178 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00179 begin2, end2, pred); }
00180
00181
00182 template<typename InputIterator1, typename InputIterator2,
00183 typename Predicate, typename IteratorTag1, typename IteratorTag2>
00184 inline bool
00185 lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
00186 InputIterator2 begin2, InputIterator2 end2,
00187 Predicate pred, IteratorTag1, IteratorTag2)
00188 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00189 begin2, end2, pred); }
00190
00191
00192
00193 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00194 typename Predicate>
00195 bool
00196 lexicographical_compare_switch(RandomAccessIterator1 begin1,
00197 RandomAccessIterator1 end1,
00198 RandomAccessIterator2 begin2,
00199 RandomAccessIterator2 end2, Predicate pred,
00200 random_access_iterator_tag,
00201 random_access_iterator_tag)
00202 {
00203 if (_GLIBCXX_PARALLEL_CONDITION(true))
00204 {
00205 typedef iterator_traits<RandomAccessIterator1> traits1_type;
00206 typedef typename traits1_type::value_type value1_type;
00207
00208 typedef iterator_traits<RandomAccessIterator2> traits2_type;
00209 typedef typename traits2_type::value_type value2_type;
00210
00211 typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
00212 value2_type> equal_type;
00213
00214
00215 if ((end1 - begin1) < (end2 - begin2))
00216 {
00217 typedef pair<RandomAccessIterator1, RandomAccessIterator2>
00218 pair_type;
00219 pair_type mm = mismatch_switch(begin1, end1, begin2,
00220 equal_type(pred),
00221 random_access_iterator_tag(),
00222 random_access_iterator_tag());
00223
00224 return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
00225 }
00226 else
00227 {
00228 typedef pair<RandomAccessIterator2, RandomAccessIterator1>
00229 pair_type;
00230 pair_type mm = mismatch_switch(begin2, end2, begin1,
00231 equal_type(pred),
00232 random_access_iterator_tag(),
00233 random_access_iterator_tag());
00234
00235 return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
00236 }
00237 }
00238 else
00239 return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00240 begin2, end2, pred);
00241 }
00242
00243
00244 template<typename InputIterator1, typename InputIterator2>
00245 inline bool
00246 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00247 InputIterator2 begin2, InputIterator2 end2)
00248 {
00249 typedef iterator_traits<InputIterator1> traits1_type;
00250 typedef typename traits1_type::value_type value1_type;
00251 typedef typename traits1_type::iterator_category iterator1_category;
00252
00253 typedef iterator_traits<InputIterator2> traits2_type;
00254 typedef typename traits2_type::value_type value2_type;
00255 typedef typename traits2_type::iterator_category iterator2_category;
00256 typedef __gnu_parallel::less<value1_type, value2_type> less_type;
00257
00258 return lexicographical_compare_switch(begin1, end1, begin2, end2,
00259 less_type(), iterator1_category(),
00260 iterator2_category());
00261 }
00262
00263
00264 template<typename InputIterator1, typename InputIterator2,
00265 typename Predicate>
00266 inline bool
00267 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00268 InputIterator2 begin2, InputIterator2 end2,
00269 Predicate pred)
00270 {
00271 typedef iterator_traits<InputIterator1> traits1_type;
00272 typedef typename traits1_type::iterator_category iterator1_category;
00273
00274 typedef iterator_traits<InputIterator2> traits2_type;
00275 typedef typename traits2_type::iterator_category iterator2_category;
00276
00277 return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
00278 iterator1_category(),
00279 iterator2_category());
00280 }
00281 }
00282 }
00283
00284 #endif