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 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 { return mismatch(begin1, end1, begin2, pred).first == end1; }
00158
00159
00160 template<typename InputIterator1, typename InputIterator2>
00161 inline bool
00162 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00163 InputIterator2 begin2, InputIterator2 end2,
00164 __gnu_parallel::sequential_tag)
00165 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00166 begin2, end2); }
00167
00168
00169 template<typename InputIterator1, typename InputIterator2,
00170 typename Predicate>
00171 inline bool
00172 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00173 InputIterator2 begin2, InputIterator2 end2,
00174 Predicate pred, __gnu_parallel::sequential_tag)
00175 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00176 begin2, end2, pred); }
00177
00178
00179 template<typename InputIterator1, typename InputIterator2,
00180 typename Predicate, typename IteratorTag1, typename IteratorTag2>
00181 inline bool
00182 lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
00183 InputIterator2 begin2, InputIterator2 end2,
00184 Predicate pred, IteratorTag1, IteratorTag2)
00185 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00186 begin2, end2, pred); }
00187
00188
00189
00190 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00191 typename Predicate>
00192 bool
00193 lexicographical_compare_switch(RandomAccessIterator1 begin1,
00194 RandomAccessIterator1 end1,
00195 RandomAccessIterator2 begin2,
00196 RandomAccessIterator2 end2, Predicate pred,
00197 random_access_iterator_tag,
00198 random_access_iterator_tag)
00199 {
00200 if (_GLIBCXX_PARALLEL_CONDITION(true))
00201 {
00202 typedef iterator_traits<RandomAccessIterator1> traits1_type;
00203 typedef typename traits1_type::value_type value1_type;
00204
00205 typedef iterator_traits<RandomAccessIterator2> traits2_type;
00206 typedef typename traits2_type::value_type value2_type;
00207
00208 typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
00209 value2_type> equal_type;
00210
00211
00212 if ((end1 - begin1) < (end2 - begin2))
00213 {
00214 typedef pair<RandomAccessIterator1, RandomAccessIterator2>
00215 pair_type;
00216 pair_type mm = mismatch_switch(begin1, end1, begin2,
00217 equal_type(pred),
00218 random_access_iterator_tag(),
00219 random_access_iterator_tag());
00220
00221 return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
00222 }
00223 else
00224 {
00225 typedef pair<RandomAccessIterator2, RandomAccessIterator1>
00226 pair_type;
00227 pair_type mm = mismatch_switch(begin2, end2, begin1,
00228 equal_type(pred),
00229 random_access_iterator_tag(),
00230 random_access_iterator_tag());
00231
00232 return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
00233 }
00234 }
00235 else
00236 return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
00237 begin2, end2, pred);
00238 }
00239
00240
00241 template<typename InputIterator1, typename InputIterator2>
00242 inline bool
00243 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00244 InputIterator2 begin2, InputIterator2 end2)
00245 {
00246 typedef iterator_traits<InputIterator1> traits1_type;
00247 typedef typename traits1_type::value_type value1_type;
00248 typedef typename traits1_type::iterator_category iterator1_category;
00249
00250 typedef iterator_traits<InputIterator2> traits2_type;
00251 typedef typename traits2_type::value_type value2_type;
00252 typedef typename traits2_type::iterator_category iterator2_category;
00253 typedef __gnu_parallel::less<value1_type, value2_type> less_type;
00254
00255 return lexicographical_compare_switch(begin1, end1, begin2, end2,
00256 less_type(), iterator1_category(),
00257 iterator2_category());
00258 }
00259
00260
00261 template<typename InputIterator1, typename InputIterator2,
00262 typename Predicate>
00263 inline bool
00264 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
00265 InputIterator2 begin2, InputIterator2 end2,
00266 Predicate pred)
00267 {
00268 typedef iterator_traits<InputIterator1> traits1_type;
00269 typedef typename traits1_type::iterator_category iterator1_category;
00270
00271 typedef iterator_traits<InputIterator2> traits2_type;
00272 typedef typename traits2_type::iterator_category iterator2_category;
00273
00274 return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
00275 iterator1_category(),
00276 iterator2_category());
00277 }
00278 }
00279 }
00280
00281 #endif