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
38template <class _InputIter1, class _InputIter2>
39bool 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
55template <class _InputIter1, class _InputIter2, class _Compare>
56bool 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
77template <class _InputIter1, class _InputIter2>
78int __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
100template <class _InputIter1, class _InputIter2>
101int 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
111template <class _RandomAccessIter, class _Tp>
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
147inline char*
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}
152inline const char*
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
158template <class _RandomAccessIter, class _Predicate>
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
194template <class _InputIter, class _Tp>
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
202template <class _InputIter, class _Predicate>
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
213template <class _InputIter, class _Predicate>
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
220template <class _InputIter, class _Tp>
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
226template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
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
271template <class _Tp>
272struct _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
286template <class _Tp1, class _Tp2>
287inline bool __stlp_eq(_Tp1 __val1, _Tp2 __val2)
288{ return __val1 == __val2; }
289
290#if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
291template <class _Tp>
292inline bool __stlp_eq(_Tp, _Tp)
293{ return true; }
294#endif
295
296template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
297inline _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
317template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
318inline _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
326template <class _InputIter, class _ForwardIter, class _Tp1, class _Tp2>
327inline _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
338template <class _InputIter, class _ForwardIter>
339inline _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.
347template <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.
367template <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
403template <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
431template <class _ForwardIter1, class _ForwardIter2,
432          class _BinaryPredicate>
433_ForwardIter1
434find_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
452template <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