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