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 _IIter1, typename _IIter2>
00054 inline pair<_IIter1, _IIter2>
00055 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00056 __gnu_parallel::sequential_tag)
00057 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2); }
00058
00059
00060 template<typename _IIter1, typename _IIter2, typename _Predicate>
00061 inline pair<_IIter1, _IIter2>
00062 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00063 _Predicate __pred, __gnu_parallel::sequential_tag)
00064 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred); }
00065
00066
00067 template<typename _IIter1, typename _IIter2,
00068 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
00069 inline pair<_IIter1, _IIter2>
00070 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00071 _Predicate __pred, _IteratorTag1, _IteratorTag2)
00072 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred); }
00073
00074
00075 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
00076 pair<_RAIter1, _RAIter2>
00077 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
00078 _RAIter2 __begin2, _Predicate __pred,
00079 random_access_iterator_tag, random_access_iterator_tag)
00080 {
00081 if (_GLIBCXX_PARALLEL_CONDITION(true))
00082 {
00083 _RAIter1 __res =
00084 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
00085 __gnu_parallel::
00086 __mismatch_selector()).first;
00087 return make_pair(__res , __begin2 + (__res - __begin1));
00088 }
00089 else
00090 return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred);
00091 }
00092
00093
00094 template<typename _IIter1, typename _IIter2>
00095 inline pair<_IIter1, _IIter2>
00096 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
00097 {
00098 typedef std::iterator_traits<_IIter1> _Iterator1Traits;
00099 typedef std::iterator_traits<_IIter2> _Iterator2Traits;
00100 typedef typename _Iterator1Traits::value_type _ValueType1;
00101 typedef typename _Iterator2Traits::value_type _ValueType2;
00102 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
00103 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
00104
00105 typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo;
00106
00107 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
00108 _IteratorCategory1(), _IteratorCategory2());
00109 }
00110
00111
00112 template<typename _IIter1, typename _IIter2, typename _Predicate>
00113 inline pair<_IIter1, _IIter2>
00114 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00115 _Predicate __pred)
00116 {
00117 typedef std::iterator_traits<_IIter1> _Iterator1Traits;
00118 typedef std::iterator_traits<_IIter2> _Iterator2Traits;
00119 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
00120 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
00121
00122 return __mismatch_switch(__begin1, __end1, __begin2, __pred,
00123 _IteratorCategory1(), _IteratorCategory2());
00124 }
00125
00126
00127 template<typename _IIter1, typename _IIter2>
00128 inline bool
00129 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00130 __gnu_parallel::sequential_tag)
00131 { return _GLIBCXX_STD_P::equal(__begin1, __end1, __begin2); }
00132
00133
00134 template<typename _IIter1, typename _IIter2, typename _Predicate>
00135 inline bool
00136 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00137 _Predicate __pred, __gnu_parallel::sequential_tag)
00138 { return _GLIBCXX_STD_P::equal(__begin1, __end1, __begin2, __pred); }
00139
00140
00141 template<typename _IIter1, typename _IIter2>
00142 inline bool
00143 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
00144 {
00145 return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2).first
00146 == __end1;
00147 }
00148
00149
00150 template<typename _IIter1, typename _IIter2, typename _Predicate>
00151 inline bool
00152 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
00153 _Predicate __pred)
00154 {
00155 return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred).first
00156 == __end1;
00157 }
00158
00159
00160 template<typename _IIter1, typename _IIter2>
00161 inline bool
00162 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00163 _IIter2 __begin2, _IIter2 __end2,
00164 __gnu_parallel::sequential_tag)
00165 { return _GLIBCXX_STD_P::lexicographical_compare(__begin1, __end1,
00166 __begin2, __end2); }
00167
00168
00169 template<typename _IIter1, typename _IIter2, typename _Predicate>
00170 inline bool
00171 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00172 _IIter2 __begin2, _IIter2 __end2,
00173 _Predicate __pred, __gnu_parallel::sequential_tag)
00174 { return _GLIBCXX_STD_P::lexicographical_compare(
00175 __begin1, __end1, __begin2, __end2, __pred); }
00176
00177
00178 template<typename _IIter1, typename _IIter2,
00179 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
00180 inline bool
00181 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
00182 _IIter2 __begin2, _IIter2 __end2,
00183 _Predicate __pred,
00184 _IteratorTag1, _IteratorTag2)
00185 { return _GLIBCXX_STD_P::lexicographical_compare(
00186 __begin1, __end1, __begin2, __end2, __pred); }
00187
00188
00189
00190 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
00191 bool
00192 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
00193 _RAIter2 __begin2, _RAIter2 __end2,
00194 _Predicate __pred,
00195 random_access_iterator_tag,
00196 random_access_iterator_tag)
00197 {
00198 if (_GLIBCXX_PARALLEL_CONDITION(true))
00199 {
00200 typedef iterator_traits<_RAIter1> _TraitsType1;
00201 typedef typename _TraitsType1::value_type _ValueType1;
00202
00203 typedef iterator_traits<_RAIter2> _TraitsType2;
00204 typedef typename _TraitsType2::value_type _ValueType2;
00205
00206 typedef __gnu_parallel::
00207 _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
00208 _EqualFromLessCompare;
00209
00210
00211 if ((__end1 - __begin1) < (__end2 - __begin2))
00212 {
00213 typedef pair<_RAIter1, _RAIter2> _SpotType;
00214 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
00215 _EqualFromLessCompare(__pred),
00216 random_access_iterator_tag(),
00217 random_access_iterator_tag());
00218
00219 return (__mm.first == __end1)
00220 || bool(__pred(*__mm.first, *__mm.second));
00221 }
00222 else
00223 {
00224 typedef pair<_RAIter2, _RAIter1> _SpotType;
00225 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
00226 _EqualFromLessCompare(__pred),
00227 random_access_iterator_tag(),
00228 random_access_iterator_tag());
00229
00230 return (__mm.first != __end2)
00231 && bool(__pred(*__mm.second, *__mm.first));
00232 }
00233 }
00234 else
00235 return _GLIBCXX_STD_P::lexicographical_compare(
00236 __begin1, __end1, __begin2, __end2, __pred);
00237 }
00238
00239
00240 template<typename _IIter1, typename _IIter2>
00241 inline bool
00242 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00243 _IIter2 __begin2, _IIter2 __end2)
00244 {
00245 typedef iterator_traits<_IIter1> _TraitsType1;
00246 typedef typename _TraitsType1::value_type _ValueType1;
00247 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00248
00249 typedef iterator_traits<_IIter2> _TraitsType2;
00250 typedef typename _TraitsType2::value_type _ValueType2;
00251 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00252 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
00253
00254 return __lexicographical_compare_switch(
00255 __begin1, __end1, __begin2, __end2, _LessType(),
00256 _IteratorCategory1(), _IteratorCategory2());
00257 }
00258
00259
00260 template<typename _IIter1, typename _IIter2, typename _Predicate>
00261 inline bool
00262 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
00263 _IIter2 __begin2, _IIter2 __end2,
00264 _Predicate __pred)
00265 {
00266 typedef iterator_traits<_IIter1> _TraitsType1;
00267 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00268
00269 typedef iterator_traits<_IIter2> _TraitsType2;
00270 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00271
00272 return __lexicographical_compare_switch(
00273 __begin1, __end1, __begin2, __end2, __pred,
00274 _IteratorCategory1(), _IteratorCategory2());
00275 }
00276 }
00277 }
00278
00279 #endif