1 /*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
23 *
24 */
25 #ifndef _STLP_ALGOBASE_C
26 #define _STLP_ALGOBASE_C
27
28 #ifndef _STLP_INTERNAL_ALGOBASE_H
29 # include <stl/_algobase.h>
30 #endif
31
32 _STLP_BEGIN_NAMESPACE
33
34 template <class _InputIter1, class _InputIter2>
lexicographical_compare(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2)35 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
36 _InputIter2 __first2, _InputIter2 __last2) {
37 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
38 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
39 for ( ; __first1 != __last1 && __first2 != __last2
40 ; ++__first1, ++__first2) {
41 if (*__first1 < *__first2) {
42 return true;
43 }
44 if (*__first2 < *__first1)
45 return false;
46 }
47 return __first1 == __last1 && __first2 != __last2;
48 }
49
50 template <class _InputIter1, class _InputIter2, class _Compare>
lexicographical_compare(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2,_Compare __comp)51 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
52 _InputIter2 __first2, _InputIter2 __last2,
53 _Compare __comp) {
54 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
55 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
56 for ( ; __first1 != __last1 && __first2 != __last2
57 ; ++__first1, ++__first2) {
58 if (__comp(*__first1, *__first2)) {
59 return true;
60 }
61 if (__comp(*__first2, *__first1))
62 return false;
63 }
64 return __first1 == __last1 && __first2 != __last2;
65 }
66
67 #if !defined (_STLP_NO_EXTENSIONS)
68 _STLP_MOVE_TO_PRIV_NAMESPACE
69
70 template <class _InputIter1, class _InputIter2>
__lexicographical_compare_3way(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2)71 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
72 _InputIter2 __first2, _InputIter2 __last2) {
73 while (__first1 != __last1 && __first2 != __last2) {
74 if (*__first1 < *__first2) {
75 _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
76 return -1;
77 }
78 if (*__first2 < *__first1)
79 return 1;
80 ++__first1;
81 ++__first2;
82 }
83 if (__first2 == __last2) {
84 return !(__first1 == __last1);
85 }
86 else {
87 return -1;
88 }
89 }
90
91 _STLP_MOVE_TO_STD_NAMESPACE
92
93 template <class _InputIter1, class _InputIter2>
lexicographical_compare_3way(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2)94 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
95 _InputIter2 __first2, _InputIter2 __last2) {
96 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
97 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
98 return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
99 }
100 #endif
101
102 _STLP_MOVE_TO_PRIV_NAMESPACE
103
104 template <class _RandomAccessIter, class _Tp>
__find(_RandomAccessIter __first,_RandomAccessIter __last,const _Tp & __val,const random_access_iterator_tag &)105 _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
106 const _Tp& __val,
107 const random_access_iterator_tag &) {
108 _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
109
110 for ( ; __trip_count > 0 ; --__trip_count) {
111 if (*__first == __val) return __first;
112 ++__first;
113
114 if (*__first == __val) return __first;
115 ++__first;
116
117 if (*__first == __val) return __first;
118 ++__first;
119
120 if (*__first == __val) return __first;
121 ++__first;
122 }
123
124 switch (__last - __first) {
125 case 3:
126 if (*__first == __val) return __first;
127 ++__first;
128 case 2:
129 if (*__first == __val) return __first;
130 ++__first;
131 case 1:
132 if (*__first == __val) return __first;
133 //++__first;
134 case 0:
135 default:
136 return __last;
137 }
138 }
139
140 inline char*
__find(char * __first,char * __last,char __val,const random_access_iterator_tag &)141 __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
142 void *res = memchr(__first, __val, __last - __first);
143 return res != 0 ? __STATIC_CAST(char*, res) : __last;
144 }
145 inline const char*
__find(const char * __first,const char * __last,char __val,const random_access_iterator_tag &)146 __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
147 const void *res = memchr(__first, __val, __last - __first);
148 return res != 0 ? __STATIC_CAST(const char*, res) : __last;
149 }
150
151 template <class _RandomAccessIter, class _Predicate>
__find_if(_RandomAccessIter __first,_RandomAccessIter __last,_Predicate __pred,const random_access_iterator_tag &)152 _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
153 _Predicate __pred,
154 const random_access_iterator_tag &) {
155 _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
156
157 for ( ; __trip_count > 0 ; --__trip_count) {
158 if (__pred(*__first)) return __first;
159 ++__first;
160
161 if (__pred(*__first)) return __first;
162 ++__first;
163
164 if (__pred(*__first)) return __first;
165 ++__first;
166
167 if (__pred(*__first)) return __first;
168 ++__first;
169 }
170
171 switch(__last - __first) {
172 case 3:
173 if (__pred(*__first)) return __first;
174 ++__first;
175 case 2:
176 if (__pred(*__first)) return __first;
177 ++__first;
178 case 1:
179 if (__pred(*__first)) return __first;
180 //++__first;
181 case 0:
182 default:
183 return __last;
184 }
185 }
186
187 template <class _InputIter, class _Tp>
__find(_InputIter __first,_InputIter __last,const _Tp & __val,const input_iterator_tag &)188 _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
189 const _Tp& __val,
190 const input_iterator_tag &) {
191 while (__first != __last && !(*__first == __val)) ++__first;
192 return __first;
193 }
194
195 template <class _InputIter, class _Predicate>
__find_if(_InputIter __first,_STLP_MPW_EXTRA_CONST _InputIter __last,_Predicate __pred,const input_iterator_tag &)196 _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
197 _Predicate __pred,
198 const input_iterator_tag &) {
199 while (__first != __last && !__pred(*__first))
200 ++__first;
201 return __first;
202 }
203
204 _STLP_MOVE_TO_STD_NAMESPACE
205
206 template <class _InputIter, class _Predicate>
find_if(_InputIter __first,_InputIter __last,_Predicate __pred)207 _InputIter find_if(_InputIter __first, _InputIter __last,
208 _Predicate __pred) {
209 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
210 return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
211 }
212
213 template <class _InputIter, class _Tp>
find(_InputIter __first,_InputIter __last,const _Tp & __val)214 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
215 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
216 return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
217 }
218
219 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
search(_ForwardIter1 __first1,_ForwardIter1 __last1,_ForwardIter2 __first2,_ForwardIter2 __last2,_BinaryPred __pred)220 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
221 _ForwardIter2 __first2, _ForwardIter2 __last2,
222 _BinaryPred __pred) {
223 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
224 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
225 // Test for empty ranges
226 if (__first1 == __last1 || __first2 == __last2)
227 return __first1;
228
229 // Test for a pattern of length 1.
230 _ForwardIter2 __p1(__first2);
231
232 if ( ++__p1 == __last2 ) {
233 while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
234 ++__first1;
235 }
236 return __first1;
237 }
238
239 // General case.
240
241 for ( ; ; ) { // __first1 != __last1 will be checked below
242 while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
243 ++__first1;
244 }
245 if (__first1 == __last1) {
246 return __last1;
247 }
248 _ForwardIter2 __p = __p1;
249 _ForwardIter1 __current = __first1;
250 if (++__current == __last1) return __last1;
251
252 while (__pred(*__current, *__p)) {
253 if (++__p == __last2)
254 return __first1;
255 if (++__current == __last1)
256 return __last1;
257 }
258
259 ++__first1;
260 }
261 return __first1;
262 }
263
264 _STLP_MOVE_TO_PRIV_NAMESPACE
265
266 // find_first_of, with and without an explicitly supplied comparison function.
267 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
__find_first_of(_InputIter __first1,_InputIter __last1,_ForwardIter __first2,_ForwardIter __last2,_BinaryPredicate __comp)268 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
269 _ForwardIter __first2, _ForwardIter __last2,
270 _BinaryPredicate __comp) {
271 for ( ; __first1 != __last1; ++__first1) {
272 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
273 if (__comp(*__first1, *__iter)) {
274 return __first1;
275 }
276 }
277 }
278 return __last1;
279 }
280
281 // find_end, with and without an explicitly supplied comparison function.
282 // Search [first2, last2) as a subsequence in [first1, last1), and return
283 // the *last* possible match. Note that find_end for bidirectional iterators
284 // is much faster than for forward iterators.
285
286 // find_end for forward iterators.
287 template <class _ForwardIter1, class _ForwardIter2,
288 class _BinaryPredicate>
__find_end(_ForwardIter1 __first1,_ForwardIter1 __last1,_ForwardIter2 __first2,_ForwardIter2 __last2,const forward_iterator_tag &,const forward_iterator_tag &,_BinaryPredicate __comp)289 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
290 _ForwardIter2 __first2, _ForwardIter2 __last2,
291 const forward_iterator_tag &, const forward_iterator_tag &,
292 _BinaryPredicate __comp) {
293 if (__first2 == __last2)
294 return __last1;
295 else {
296 _ForwardIter1 __result = __last1;
297 for (;;) {
298 _ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2, __comp);
299 if (__new_result == __last1)
300 return __result;
301 else {
302 __result = __new_result;
303 __first1 = __new_result;
304 ++__first1;
305 }
306 }
307 }
308 }
309
310 _STLP_MOVE_TO_STD_NAMESPACE
311
312 // find_end for bidirectional iterators. Requires partial specialization.
313 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
314
315 # ifndef _STLP_INTERNAL_ITERATOR_H
316 _STLP_END_NAMESPACE
317 # include <stl/_iterator.h>
318 _STLP_BEGIN_NAMESPACE
319 # endif /*_STLP_INTERNAL_ITERATOR_H*/
320
321 _STLP_MOVE_TO_PRIV_NAMESPACE
322
323 template <class _BidirectionalIter1, class _BidirectionalIter2,
324 class _BinaryPredicate>
325 _BidirectionalIter1
__find_end(_BidirectionalIter1 __first1,_BidirectionalIter1 __last1,_BidirectionalIter2 __first2,_BidirectionalIter2 __last2,const bidirectional_iterator_tag &,const bidirectional_iterator_tag &,_BinaryPredicate __comp)326 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
327 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
328 const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
329 _BinaryPredicate __comp) {
330 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
331 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
332
333 _RevIter1 __rlast1(__first1);
334 _RevIter2 __rlast2(__first2);
335 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
336 _RevIter2(__last2), __rlast2,
337 __comp);
338
339 if (__rresult == __rlast1)
340 return __last1;
341 else {
342 _BidirectionalIter1 __result = __rresult.base();
343 advance(__result, -distance(__first2, __last2));
344 return __result;
345 }
346 }
347
348 _STLP_MOVE_TO_STD_NAMESPACE
349 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
350
351 template <class _ForwardIter1, class _ForwardIter2,
352 class _BinaryPredicate>
353 _ForwardIter1
find_end(_ForwardIter1 __first1,_ForwardIter1 __last1,_ForwardIter2 __first2,_ForwardIter2 __last2,_BinaryPredicate __comp)354 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
355 _ForwardIter2 __first2, _ForwardIter2 __last2,
356 _BinaryPredicate __comp) {
357 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
358 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
359 return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
360 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
361 _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
362 _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
363 #else
364 forward_iterator_tag(),
365 forward_iterator_tag(),
366 #endif
367 __comp);
368 }
369
370 _STLP_MOVE_TO_PRIV_NAMESPACE
371
372 template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
__lower_bound(_ForwardIter __first,_ForwardIter __last,const _Tp & __val,_Compare1 __comp1,_Compare2 __comp2,_Distance *)373 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
374 _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
375 _Distance __len = distance(__first, __last);
376 _Distance __half;
377 _ForwardIter __middle;
378
379 while (__len > 0) {
380 __half = __len >> 1;
381 __middle = __first;
382 advance(__middle, __half);
383 if (__comp1(*__middle, __val)) {
384 _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
385 __first = __middle;
386 ++__first;
387 __len = __len - __half - 1;
388 }
389 else
390 __len = __half;
391 }
392 return __first;
393 }
394
395 _STLP_MOVE_TO_STD_NAMESPACE
396
397 _STLP_END_NAMESPACE
398
399 #endif /* _STLP_ALGOBASE_C */
400
401 // Local Variables:
402 // mode:C++
403 // End:
404