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 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
33 #  include <stl/_function_base.h>
34 #endif
35 
36 _STLP_BEGIN_NAMESPACE
37 
38 template <class _InputIter1, class _InputIter2>
lexicographical_compare(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2)39 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
40                              _InputIter2 __first2, _InputIter2 __last2) {
41   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
42   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
43   for ( ; __first1 != __last1 && __first2 != __last2
44         ; ++__first1, ++__first2) {
45     if (*__first1 < *__first2) {
46       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
47       return true;
48     }
49     if (*__first2 < *__first1)
50       return false;
51   }
52   return __first1 == __last1 && __first2 != __last2;
53 }
54 
55 template <class _InputIter1, class _InputIter2, class _Compare>
lexicographical_compare(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2,_Compare __comp)56 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
57                              _InputIter2 __first2, _InputIter2 __last2,
58                              _Compare __comp) {
59   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
60   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
61   for ( ; __first1 != __last1 && __first2 != __last2
62         ; ++__first1, ++__first2) {
63     if (__comp(*__first1, *__first2)) {
64       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1),
65                            _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
66       return true;
67     }
68     if (__comp(*__first2, *__first1))
69       return false;
70   }
71   return __first1 == __last1 && __first2 != __last2;
72 }
73 
74 #if !defined (_STLP_NO_EXTENSIONS)
75 _STLP_MOVE_TO_PRIV_NAMESPACE
76 
77 template <class _InputIter1, class _InputIter2>
__lexicographical_compare_3way(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2)78 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
79                                    _InputIter2 __first2, _InputIter2 __last2) {
80   while (__first1 != __last1 && __first2 != __last2) {
81     if (*__first1 < *__first2) {
82       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
83       return -1;
84     }
85     if (*__first2 < *__first1)
86       return 1;
87     ++__first1;
88     ++__first2;
89   }
90   if (__first2 == __last2) {
91     return !(__first1 == __last1);
92   }
93   else {
94     return -1;
95   }
96 }
97 
98 _STLP_MOVE_TO_STD_NAMESPACE
99 
100 template <class _InputIter1, class _InputIter2>
lexicographical_compare_3way(_InputIter1 __first1,_InputIter1 __last1,_InputIter2 __first2,_InputIter2 __last2)101 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
102                                  _InputIter2 __first2, _InputIter2 __last2) {
103   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
104   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
105   return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
106 }
107 #endif
108 
109 _STLP_MOVE_TO_PRIV_NAMESPACE
110 
111 template <class _RandomAccessIter, class _Tp>
__find(_RandomAccessIter __first,_RandomAccessIter __last,const _Tp & __val,const random_access_iterator_tag &)112 _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
113                                            const _Tp& __val,
114                                            const random_access_iterator_tag &) {
115   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
116 
117   for ( ; __trip_count > 0 ; --__trip_count) {
118     if (*__first == __val) return __first;
119     ++__first;
120 
121     if (*__first == __val) return __first;
122     ++__first;
123 
124     if (*__first == __val) return __first;
125     ++__first;
126 
127     if (*__first == __val) return __first;
128     ++__first;
129   }
130 
131   switch (__last - __first) {
132   case 3:
133     if (*__first == __val) return __first;
134     ++__first;
135   case 2:
136     if (*__first == __val) return __first;
137     ++__first;
138   case 1:
139     if (*__first == __val) return __first;
140     //++__first;
141   case 0:
142   default:
143     return __last;
144   }
145 }
146 
147 inline char*
__find(char * __first,char * __last,char __val,const random_access_iterator_tag &)148 __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
149   void *res =  memchr(__first, __val, __last - __first);
150   return res != 0 ? __STATIC_CAST(char*, res) : __last;
151 }
152 inline const char*
__find(const char * __first,const char * __last,char __val,const random_access_iterator_tag &)153 __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
154   const void *res =  memchr(__first, __val, __last - __first);
155   return res != 0 ? __STATIC_CAST(const char*, res) : __last;
156 }
157 
158 template <class _RandomAccessIter, class _Predicate>
__find_if(_RandomAccessIter __first,_RandomAccessIter __last,_Predicate __pred,const random_access_iterator_tag &)159 _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
160                                               _Predicate __pred,
161                                               const random_access_iterator_tag &) {
162   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
163 
164   for ( ; __trip_count > 0 ; --__trip_count) {
165     if (__pred(*__first)) return __first;
166     ++__first;
167 
168     if (__pred(*__first)) return __first;
169     ++__first;
170 
171     if (__pred(*__first)) return __first;
172     ++__first;
173 
174     if (__pred(*__first)) return __first;
175     ++__first;
176   }
177 
178   switch(__last - __first) {
179   case 3:
180     if (__pred(*__first)) return __first;
181     ++__first;
182   case 2:
183     if (__pred(*__first)) return __first;
184     ++__first;
185   case 1:
186     if (__pred(*__first)) return __first;
187       //++__first;
188   case 0:
189   default:
190     return __last;
191   }
192 }
193 
194 template <class _InputIter, class _Tp>
__find(_InputIter __first,_InputIter __last,const _Tp & __val,const input_iterator_tag &)195 _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
196                                     const _Tp& __val,
197                                     const input_iterator_tag &) {
198   while (__first != __last && !(*__first == __val)) ++__first;
199   return __first;
200 }
201 
202 template <class _InputIter, class _Predicate>
__find_if(_InputIter __first,_InputIter __last,_Predicate __pred,const input_iterator_tag &)203 _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _InputIter __last,
204                                        _Predicate __pred,
205                                        const input_iterator_tag &) {
206   while (__first != __last && !__pred(*__first))
207     ++__first;
208   return __first;
209 }
210 
211 _STLP_MOVE_TO_STD_NAMESPACE
212 
213 template <class _InputIter, class _Predicate>
find_if(_InputIter __first,_InputIter __last,_Predicate __pred)214 _InputIter find_if(_InputIter __first, _InputIter __last,
215                    _Predicate __pred) {
216   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
217   return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
218 }
219 
220 template <class _InputIter, class _Tp>
find(_InputIter __first,_InputIter __last,const _Tp & __val)221 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
222   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
223   return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
224 }
225 
226 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
search(_ForwardIter1 __first1,_ForwardIter1 __last1,_ForwardIter2 __first2,_ForwardIter2 __last2,_BinaryPred __pred)227 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
228                      _ForwardIter2 __first2, _ForwardIter2 __last2,
229                      _BinaryPred  __pred) {
230   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
231   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
232   // Test for empty ranges
233   if (__first1 == __last1 || __first2 == __last2)
234     return __first1;
235 
236   // Test for a pattern of length 1.
237   _ForwardIter2 __p1(__first2);
238 
239   if ( ++__p1 == __last2 ) {
240     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
241       ++__first1;
242     }
243     return __first1;
244   }
245 
246   // General case.
247 
248   for ( ; ; ) { // __first1 != __last1 will be checked below
249     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
250       ++__first1;
251     }
252     if (__first1 == __last1) {
253       return __last1;
254     }
255     _ForwardIter2 __p = __p1;
256     _ForwardIter1 __current = __first1;
257     if (++__current == __last1) return __last1;
258 
259     while (__pred(*__current, *__p)) {
260       if (++__p == __last2)
261         return __first1;
262       if (++__current == __last1)
263         return __last1;
264     }
265     ++__first1;
266   }
267   return __first1;
268 }
269 
270 _STLP_MOVE_TO_PRIV_NAMESPACE
271 template <class _Tp>
272 struct _IsCharLikeType
273 { typedef __false_type _Ret; };
274 
275 _STLP_TEMPLATE_NULL struct _IsCharLikeType<char>
276 { typedef __true_type _Ret; };
277 
278 _STLP_TEMPLATE_NULL struct _IsCharLikeType<unsigned char>
279 { typedef __true_type _Ret; };
280 
281 #  ifndef _STLP_NO_SIGNED_BUILTINS
282 _STLP_TEMPLATE_NULL struct _IsCharLikeType<signed char>
283 { typedef __true_type _Ret; };
284 #  endif
285 
286 template <class _Tp1, class _Tp2>
287 inline bool __stlp_eq(_Tp1 __val1, _Tp2 __val2)
288 { return __val1 == __val2; }
289 
290 #if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
291 template <class _Tp>
292 inline bool __stlp_eq(_Tp, _Tp)
293 { return true; }
294 #endif
295 
296 template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
297 inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1,
298                                        _ForwardIter __first2, _ForwardIter __last2,
299                                        _Tp2*, _Predicate __pred,
300                                        const __true_type& /* _UseStrcspnLikeAlgo */) {
301   unsigned char __hints[(UCHAR_MAX + 1) / CHAR_BIT];
302   memset(__hints, 0, sizeof(__hints) / sizeof(unsigned char));
303   for (; __first2 != __last2; ++__first2) {
304     unsigned char __tmp = (unsigned char)*__first2;
305     __hints[__tmp / CHAR_BIT] |= (1 << (__tmp % CHAR_BIT));
306   }
307 
308   for (; __first1 != __last1; ++__first1) {
309     _Tp2 __tmp = (_Tp2)*__first1;
310     if (__stlp_eq(*__first1, __tmp) &&
311         __pred((__hints[(unsigned char)__tmp / CHAR_BIT] & (1 << ((unsigned char)__tmp % CHAR_BIT))) != 0))
312       break;
313   }
314   return __first1;
315 }
316 
317 template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
318 inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1,
319                                        _ForwardIter __first2, _ForwardIter __last2,
320                                        _Tp2* /* __dummy */, _Predicate /* __pred */,
321                                        const __false_type& /* _UseStrcspnLikeAlgo */) {
322   return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2,
323                                     _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));
324 }
325 
326 template <class _InputIter, class _ForwardIter, class _Tp1, class _Tp2>
327 inline _InputIter __find_first_of_aux1(_InputIter __first1, _InputIter __last1,
328                                        _ForwardIter __first2, _ForwardIter __last2,
329                                        _Tp1* __pt1, _Tp2* __pt2) {
330   typedef _STLP_TYPENAME _STLP_STD::_IsIntegral<_Tp1>::_Ret _IsIntegral;
331   typedef _STLP_TYPENAME _STLP_PRIV _IsCharLikeType<_Tp2>::_Ret _IsCharLike;
332   typedef _STLP_TYPENAME _STLP_STD::_Land2<_IsIntegral, _IsCharLike>::_Ret _UseStrcspnLikeAlgo;
333   return _STLP_PRIV __find_first_of_aux2(__first1, __last1,
334                                          __first2, __last2,
335                                          __pt2, _Identity<bool>(), _UseStrcspnLikeAlgo());
336 }
337 
338 template <class _InputIter, class _ForwardIter>
339 inline _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
340                                   _ForwardIter __first2, _ForwardIter __last2) {
341   return _STLP_PRIV __find_first_of_aux1(__first1, __last1, __first2, __last2,
342                                          _STLP_VALUE_TYPE(__first1, _InputIter),
343                                          _STLP_VALUE_TYPE(__first2, _ForwardIter));
344 }
345 
346 // find_first_of, with and without an explicitly supplied comparison function.
347 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
348 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
349                            _ForwardIter __first2, _ForwardIter __last2,
350                            _BinaryPredicate __comp) {
351   for ( ; __first1 != __last1; ++__first1) {
352     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
353       if (__comp(*__first1, *__iter)) {
354         return __first1;
355       }
356     }
357   }
358   return __last1;
359 }
360 
361 // find_end, with and without an explicitly supplied comparison function.
362 // Search [first2, last2) as a subsequence in [first1, last1), and return
363 // the *last* possible match.  Note that find_end for bidirectional iterators
364 // is much faster than for forward iterators.
365 
366 // find_end for forward iterators.
367 template <class _ForwardIter1, class _ForwardIter2,
368   class _BinaryPredicate>
369 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
370                          _ForwardIter2 __first2, _ForwardIter2 __last2,
371                          const forward_iterator_tag &, const forward_iterator_tag &,
372                          _BinaryPredicate __comp) {
373   if (__first2 == __last2)
374     return __last1;
375   else {
376     _ForwardIter1 __result = __last1;
377     for (;;) {
378       _ForwardIter1 __new_result = _STLP_STD::search(__first1, __last1, __first2, __last2, __comp);
379       if (__new_result == __last1)
380         return __result;
381       else {
382         __result = __new_result;
383         __first1 = __new_result;
384         ++__first1;
385       }
386     }
387   }
388 }
389 
390 _STLP_MOVE_TO_STD_NAMESPACE
391 
392 // find_end for bidirectional iterators.  Requires partial specialization.
393 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
394 
395 #  ifndef _STLP_INTERNAL_ITERATOR_H
396 _STLP_END_NAMESPACE
397 #    include <stl/_iterator.h>
398 _STLP_BEGIN_NAMESPACE
399 #  endif /*_STLP_INTERNAL_ITERATOR_H*/
400 
401 _STLP_MOVE_TO_PRIV_NAMESPACE
402 
403 template <class _BidirectionalIter1, class _BidirectionalIter2,
404           class _BinaryPredicate>
405 _BidirectionalIter1
406 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
407            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
408            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
409            _BinaryPredicate __comp) {
410   typedef _STLP_STD::reverse_iterator<_BidirectionalIter1> _RevIter1;
411   typedef _STLP_STD::reverse_iterator<_BidirectionalIter2> _RevIter2;
412 
413   _RevIter1 __rlast1(__first1);
414   _RevIter2 __rlast2(__first2);
415   _RevIter1 __rresult = _STLP_STD::search(_RevIter1(__last1), __rlast1,
416                                           _RevIter2(__last2), __rlast2,
417                                           __comp);
418 
419   if (__rresult == __rlast1)
420     return __last1;
421   else {
422     _BidirectionalIter1 __result = __rresult.base();
423     _STLP_STD::advance(__result, -_STLP_STD::distance(__first2, __last2));
424     return __result;
425   }
426 }
427 
428 _STLP_MOVE_TO_STD_NAMESPACE
429 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
430 
431 template <class _ForwardIter1, class _ForwardIter2,
432           class _BinaryPredicate>
433 _ForwardIter1
434 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
435          _ForwardIter2 __first2, _ForwardIter2 __last2,
436          _BinaryPredicate __comp) {
437   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
438   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
439   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
440 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
441                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
442                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
443 #else
444                                forward_iterator_tag(),
445                                forward_iterator_tag(),
446 #endif
447                                __comp);
448 }
449 
450 _STLP_MOVE_TO_PRIV_NAMESPACE
451 
452 template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
453 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
454                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
455   _Distance __len = _STLP_STD::distance(__first, __last);
456   _Distance __half;
457   _ForwardIter __middle;
458 
459   while (__len > 0) {
460     __half = __len >> 1;
461     __middle = __first;
462     _STLP_STD::advance(__middle, __half);
463     if (__comp1(*__middle, __val)) {
464       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
465       __first = __middle;
466       ++__first;
467       __len = __len - __half - 1;
468     }
469     else
470       __len = __half;
471   }
472   return __first;
473 }
474 
475 _STLP_MOVE_TO_STD_NAMESPACE
476 
477 _STLP_END_NAMESPACE
478 
479 #endif /* _STLP_ALGOBASE_C */
480 
481 // Local Variables:
482 // mode:C++
483 // End:
484