ReactOS  0.4.14-dev-114-gc8cbd56
_algobase.h
Go to the documentation of this file.
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 
26 /* NOTE: This is an internal header file, included by other STL headers.
27  * You should not attempt to use it directly.
28  */
29 
30 #ifndef _STLP_INTERNAL_ALGOBASE_H
31 #define _STLP_INTERNAL_ALGOBASE_H
32 
33 #ifndef _STLP_INTERNAL_CSTDDEF
34 # include <stl/_cstddef.h>
35 #endif
36 
37 #ifndef _STLP_INTERNAL_CSTRING
38 # include <stl/_cstring.h>
39 #endif
40 
41 #ifndef _STLP_CLIMITS
42 # include <climits>
43 #endif
44 
45 #ifndef _STLP_INTERNAL_CSTDLIB
46 # include <stl/_cstdlib.h>
47 #endif
48 
49 #ifndef _STLP_INTERNAL_PAIR_H
50 # include <stl/_pair.h>
51 #endif
52 
53 #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
54 # include <stl/_iterator_base.h>
55 #endif
56 
57 #ifndef _STLP_TYPE_TRAITS_H
58 # include <stl/type_traits.h>
59 #endif
60 
62 
63 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
65 template <class _Tp>
66 inline void __swap_aux(_Tp& __a, _Tp& __b, const __true_type& /*SwapImplemented*/) {
67  __a._M_swap_workaround(__b);
68 }
69 
70 template <class _Tp>
71 inline void __swap_aux(_Tp& __a, _Tp& __b, const __false_type& /*SwapImplemented*/) {
72  _Tp __tmp = __a;
73  __a = __b;
74  __b = __tmp;
75 }
77 #endif
78 
79 // swap and iter_swap
80 template <class _Tp>
81 inline void swap(_Tp& __a, _Tp& __b) {
82 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
83 # if !defined(__BORLANDC__)
84  typedef typename _SwapImplemented<_Tp>::_Ret _Implemented;
85 # else
86  enum { _Is = _SwapImplemented<_Tp>::_Is };
87  typedef typename __bool2type<_Is>::_Ret _Implemented;
88 # endif
89  _STLP_PRIV __swap_aux(__a, __b, _Implemented());
90 #else
91  _Tp __tmp = __a;
92  __a = __b;
93  __b = __tmp;
94 #endif
95 }
96 
98 
99 template <class _ForwardIter1, class _ForwardIter2, class _Value>
100 inline void __iter_swap_aux_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, _Value *) {
101  _Value tmp = *__i1;
102  *__i1 = *__i2;
103  *__i2 = tmp;
104 }
105 
106 template <class _ForwardIter1, class _ForwardIter2>
107 inline void __iter_swap_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, const __true_type& /*OKToSwap*/) {
108  /* namespace specification breaks access to the right swap template overload (at least for gcc) */
109  /*_STLP_STD::*/ swap(*__i1, *__i2);
110 }
111 
112 template <class _ForwardIter1, class _ForwardIter2>
113 inline void __iter_swap_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, const __false_type& /*OKToSwap*/) {
114  _STLP_PRIV __iter_swap_aux_aux( __i1, __i2, _STLP_VALUE_TYPE(__i1,_ForwardIter1) );
115 }
116 
118 
119 template <class _ForwardIter1, class _ForwardIter2>
120 inline void iter_swap(_ForwardIter1 __i1, _ForwardIter2 __i2) {
121  _STLP_PRIV __iter_swap_aux( __i1, __i2, _IsOKToSwap(_STLP_VALUE_TYPE(__i1, _ForwardIter1), _STLP_VALUE_TYPE(__i2, _ForwardIter2),
122  _STLP_IS_REF_TYPE_REAL_REF(__i1, _ForwardIter1),
123  _STLP_IS_REF_TYPE_REAL_REF(__i2, _ForwardIter2))._Answer());
124 }
125 
126 //--------------------------------------------------
127 // min and max
128 
129 #if !defined (__BORLANDC__) || defined (_STLP_USE_OWN_NAMESPACE)
130 # if (defined (__BORLANDC__) && (__BORLANDC__ < 0x580)) && !defined (__STDC__)
131 //In not ANSI mode Borland import min/max in global namespace which conflict
132 //with STLport min/max when user does a 'using namespace std' in its code
133 //(see test/unit/alg_test.cpp). To avoid this clash we simply import Borland min/max
134 //in STLport namespace.
137 # else
138 template <class _Tp>
139 inline const _Tp& (min)(const _Tp& __a, const _Tp& __b) { return __b < __a ? __b : __a; }
140 template <class _Tp>
141 inline const _Tp& (max)(const _Tp& __a, const _Tp& __b) { return __a < __b ? __b : __a; }
142 # endif
143 #endif
144 
145 # if defined (__BORLANDC__) && defined (_STLP_USE_OWN_NAMESPACE)
146 inline unsigned long (min) (unsigned long __a, unsigned long __b) { return __b < __a ? __b : __a; }
147 inline unsigned long (max) (unsigned long __a, unsigned long __b) { return __a < __b ? __b : __a; }
148 # endif
149 
150 # if !defined (__BORLANDC__) || (__BORLANDC__ < 0x590)
151 template <class _Tp, class _Compare>
152 inline const _Tp& (min)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
153  return __comp(__b, __a) ? __b : __a;
154 }
155 
156 template <class _Tp, class _Compare>
157 inline const _Tp& (max)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
158  return __comp(__a, __b) ? __b : __a;
159 }
160 # else
161 template <class _Tp, class _Compare>
162 inline const _Tp (min)(const _Tp __a, const _Tp __b, _Compare __comp) {
163  return __comp(__b, __a) ? __b : __a;
164 }
165 
166 template <class _Tp, class _Compare>
167 inline const _Tp (max)(const _Tp __a, const _Tp __b, _Compare __comp) {
168  return __comp(__a, __b) ? __b : __a;
169 }
170 # endif
171 
172 //--------------------------------------------------
173 // copy
174 
175 // All of these auxiliary functions serve two purposes. (1) Replace
176 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
177 // because the input and output ranges are permitted to overlap.)
178 // (2) If we're using random access iterators, then write the loop as
179 // a for loop with an explicit count.
180 
182 
183 template <class _InputIter, class _OutputIter, class _Distance>
184 inline _OutputIter __copy(_InputIter __first, _InputIter __last,
185  _OutputIter __result, const input_iterator_tag &, _Distance*) {
186  for ( ; __first != __last; ++__result, ++__first)
187  *__result = *__first;
188  return __result;
189 }
190 
191 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
192 template <class _InputIter, class _OutputIter, class _Distance>
193 inline _OutputIter __copy(_InputIter __first, _InputIter __last,
194  _OutputIter __result, const forward_iterator_tag &, _Distance* ) {
195  for ( ; __first != __last; ++__result, ++__first)
196  *__result = *__first;
197  return __result;
198 }
199 
200 template <class _InputIter, class _OutputIter, class _Distance>
201 inline _OutputIter __copy(_InputIter __first, _InputIter __last,
202  _OutputIter __result, const bidirectional_iterator_tag &, _Distance* ) {
203  for ( ; __first != __last; ++__result, ++__first)
204  *__result = *__first;
205  return __result;
206 }
207 #endif
208 
209 template <class _RandomAccessIter, class _OutputIter, class _Distance>
210 inline _OutputIter
211 __copy(_RandomAccessIter __first, _RandomAccessIter __last,
212  _OutputIter __result, const random_access_iterator_tag &, _Distance*) {
213  for (_Distance __n = __last - __first; __n > 0; --__n) {
214  *__result = *__first;
215  ++__first;
216  ++__result;
217  }
218  return __result;
219 }
220 
221 inline void*
222 __copy_trivial(const void* __first, const void* __last, void* __result) {
223  size_t __n = (const char*)__last - (const char*)__first;
224  return __n ? (void *)((char*)memmove(__result, __first, __n) + __n) : __result;
225 }
226 
227 //--------------------------------------------------
228 // copy_backward auxiliary functions
229 
230 template <class _BidirectionalIter1, class _BidirectionalIter2,
231  class _Distance>
232 inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
233  _BidirectionalIter1 __last,
234  _BidirectionalIter2 __result,
236  _Distance*) {
237  while (__first != __last)
238  *--__result = *--__last;
239  return __result;
240 }
241 
242 template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
243 inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,
244  _RandomAccessIter __last,
245  _BidirectionalIter __result,
247  _Distance*) {
248  for (_Distance __n = __last - __first; __n > 0; --__n)
249  *--__result = *--__last;
250  return __result;
251 }
252 
253 inline void*
254 __copy_trivial_backward(const void* __first, const void* __last, void* __result) {
255  const ptrdiff_t _Num = (const char*)__last - (const char*)__first;
256  return (_Num > 0) ? memmove((char*)__result - _Num, __first, _Num) : __result ;
257 }
258 
259 template <class _InputIter, class _OutputIter>
260 inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
261  const __false_type& /*IsOKToMemCpy*/) {
262  return _STLP_PRIV __copy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0);
263 }
264 template <class _InputIter, class _OutputIter>
265 inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
266  const __true_type& /*IsOKToMemCpy*/) {
267  // we know they all pointers, so this cast is OK
268  // return (_OutputIter)__copy_trivial(&(*__first), &(*__last), &(*__result));
269  return (_OutputIter)_STLP_PRIV __copy_trivial(__first, __last, __result);
270 }
271 
272 template <class _InputIter, class _OutputIter>
273 inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
274  const __true_type& /*BothPtrType*/) {
275  return _STLP_PRIV __copy_ptrs(__first, __last, __result,
276  _UseTrivialCopy(_STLP_VALUE_TYPE(__first, _InputIter),
277  _STLP_VALUE_TYPE(__result, _OutputIter))._Answer());
278 }
279 
280 template <class _InputIter, class _OutputIter>
281 inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
282  const __false_type& /*BothPtrType*/) {
283  return _STLP_PRIV __copy(__first, __last, __result,
284  _STLP_ITERATOR_CATEGORY(__first, _InputIter),
285  _STLP_DISTANCE_TYPE(__first, _InputIter));
286 }
287 
289 
290 template <class _InputIter, class _OutputIter>
291 inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
292  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
294 }
295 
297 
298 template <class _InputIter, class _OutputIter>
299 inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last,
300  _OutputIter __result, const __false_type& /*TrivialAssignment*/) {
301  return _STLP_PRIV __copy_backward(__first, __last, __result,
302  _STLP_ITERATOR_CATEGORY(__first, _InputIter),
303  _STLP_DISTANCE_TYPE(__first, _InputIter));
304 }
305 template <class _InputIter, class _OutputIter>
306 inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last,
307  _OutputIter __result, const __true_type& /*TrivialAssignment*/) {
308  return (_OutputIter)_STLP_PRIV __copy_trivial_backward(__first, __last, __result);
309 }
310 
311 template <class _InputIter, class _OutputIter>
312 inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
313  return _STLP_PRIV __copy_backward(__first, __last, __result,
314  _STLP_ITERATOR_CATEGORY(__first,_InputIter),
315  _STLP_DISTANCE_TYPE(__first, _InputIter));
316 }
317 
318 template <class _InputIter, class _OutputIter>
319 inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
320  return _STLP_PRIV __copy_backward_ptrs(__first, __last, __result,
321  _UseTrivialCopy(_STLP_VALUE_TYPE(__first, _InputIter),
322  _STLP_VALUE_TYPE(__result, _OutputIter))._Answer());
323 }
324 
326 
327 template <class _InputIter, class _OutputIter>
328 inline _OutputIter copy_backward(_InputIter __first, _InputIter __last, _OutputIter __result) {
329  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
331 }
332 
333 #if !defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_SIMULATE_PARTIAL_SPEC_FOR_TYPE_TRAITS)
334 # define _STLP_DECLARE_COPY_TRIVIAL(_Tp) \
335 inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) \
336 { return (_Tp*)_STLP_PRIV __copy_trivial(__first, __last, __result); } \
337 inline _Tp* copy_backward(const _Tp* __first, const _Tp* __last, _Tp* __result) \
338 { return (_Tp*)_STLP_PRIV __copy_trivial_backward(__first, __last, __result); }
339 
340 # if !defined (_STLP_NO_BOOL)
342 # endif
344 # if !defined (_STLP_NO_SIGNED_BUILTINS)
345 _STLP_DECLARE_COPY_TRIVIAL(signed char)
346 # endif
347 _STLP_DECLARE_COPY_TRIVIAL(unsigned char)
349 _STLP_DECLARE_COPY_TRIVIAL(unsigned short)
351 _STLP_DECLARE_COPY_TRIVIAL(unsigned int)
353 _STLP_DECLARE_COPY_TRIVIAL(unsigned long)
354 # if !defined(_STLP_NO_WCHAR_T) && !defined (_STLP_WCHAR_T_IS_USHORT)
356 # endif
357 # if defined (_STLP_LONG_LONG)
360 # endif
363 # if !defined (_STLP_NO_LONG_DOUBLE)
364 _STLP_DECLARE_COPY_TRIVIAL(long double)
365 # endif
366 # undef _STLP_DECLARE_COPY_TRIVIAL
367 #endif
368 
369 //--------------------------------------------------
370 // copy_n (not part of the C++ standard)
371 
372 #if !defined (_STLP_NO_EXTENSIONS)
374 
375 template <class _InputIter, class _Size, class _OutputIter>
376 _STLP_INLINE_LOOP _STLP_STD::pair<_InputIter, _OutputIter>
377 __copy_n(_InputIter __first, _Size __count, _OutputIter __result,
378  const input_iterator_tag &) {
379  for ( ; __count > 0; --__count) {
380  *__result = *__first;
381  ++__first;
382  ++__result;
383  }
384  return _STLP_STD::pair<_InputIter, _OutputIter>(__first, __result);
385 }
386 
387 template <class _RAIter, class _Size, class _OutputIter>
388 inline _STLP_STD::pair<_RAIter, _OutputIter>
389 __copy_n(_RAIter __first, _Size __count, _OutputIter __result,
390  const random_access_iterator_tag &) {
391  _RAIter __last = __first + __count;
392  return _STLP_STD::pair<_RAIter, _OutputIter>(__last, _STLP_STD::copy(__first, __last, __result));
393 }
394 
396 
397 template <class _InputIter, class _Size, class _OutputIter>
399 copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
400  _STLP_FIX_LITERAL_BUG(__first)
401  return _STLP_PRIV __copy_n(__first, __count, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
402 }
403 #endif
404 
405 //--------------------------------------------------
406 // fill and fill_n
408 
409 template <class _ForwardIter, class _Tp>
411 void __fill_fwd(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
412  for ( ; __first != __last; ++__first)
413  *__first = __val;
414 }
415 
416 template <class _ForwardIter, class _Tp, class _Distance>
417 inline void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
418  const input_iterator_tag &, _Distance*) {
419  _STLP_PRIV __fill_fwd(__first, __last, __val);
420 }
421 
422 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
423 template <class _ForwardIter, class _Tp, class _Distance>
425 void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
426  const forward_iterator_tag &, _Distance*) {
427  _STLP_PRIV __fill_fwd(__first, __last, __val);
428 }
429 
430 template <class _ForwardIter, class _Tp, class _Distance>
432 void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
433  const bidirectional_iterator_tag &, _Distance*) {
434  _STLP_PRIV __fill_fwd(__first, __last, __val);
435 }
436 #endif
437 
438 template <class _RandomAccessIter, class _Tp, class _Distance>
440 void __fill(_RandomAccessIter __first, _RandomAccessIter __last, const _Tp& __val,
441  const random_access_iterator_tag &, _Distance*) {
442  for (_Distance __n = __last - __first ; __n > 0; ++__first, --__n)
443  *__first = __val;
444 }
445 
447 
448 template <class _ForwardIter, class _Tp>
449 inline void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
450  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
451  _STLP_PRIV __fill(__first, __last, __val,
452  _STLP_ITERATOR_CATEGORY(__first, _ForwardIter),
453  _STLP_DISTANCE_TYPE(__first, _ForwardIter));
454 }
455 
456 // Specialization: for one-byte types we can use memset.
457 inline void fill(unsigned char* __first, unsigned char* __last,
458  const unsigned char& __val) {
459  unsigned char __tmp = __val;
460  memset(__first, __tmp, __last - __first);
461 }
462 #if !defined (_STLP_NO_SIGNED_BUILTINS)
463 inline void fill(signed char* __first, signed char* __last,
464  const signed char& __val) {
465  signed char __tmp = __val;
466  memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
467 }
468 #endif
469 inline void fill(char* __first, char* __last, const char& __val) {
470  char __tmp = __val;
471  memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
472 }
473 
475 
476 template <class _OutputIter, class _Size, class _Tp>
478 _OutputIter __fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
479  _STLP_FIX_LITERAL_BUG(__first)
480  for ( ; __n > 0; --__n, ++__first)
481  *__first = __val;
482  return __first;
483 }
484 
485 #if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
486 template <class _Size>
487 inline unsigned char* __fill_n(unsigned char* __first, _Size __n,
488  const unsigned char& __val) {
489  _STLP_STD::fill(__first, __first + __n, __val);
490  return __first + __n;
491 }
492 #if !defined (_STLP_NO_SIGNED_BUILTINS)
493 template <class _Size>
494 inline signed char* __fill_n(signed char* __first, _Size __n,
495  const signed char& __val) {
496  _STLP_STD::fill(__first, __first + __n, __val);
497  return __first + __n;
498 }
499 #endif
500 template <class _Size>
501 inline char* __fill_n(char* __first, _Size __n,
502  const char& __val) {
503  _STLP_STD::fill(__first, __first + __n, __val);
504  return __first + __n;
505 }
506 #endif
507 
509 
510 template <class _OutputIter, class _Size, class _Tp>
511 inline void fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
512  _STLP_FIX_LITERAL_BUG(__first)
513  _STLP_PRIV __fill_n(__first, __n, __val);
514 }
515 
516 
517 //--------------------------------------------------
518 // equal and mismatch
519 
520 template <class _InputIter1, class _InputIter2>
522 _STLP_STD::pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
523  _InputIter1 __last1,
524  _InputIter2 __first2) {
525  _STLP_FIX_LITERAL_BUG(__first2)
526  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
527  while (__first1 != __last1 && *__first1 == *__first2) {
528  ++__first1;
529  ++__first2;
530  }
531  return _STLP_STD::pair<_InputIter1, _InputIter2>(__first1, __first2);
532 }
533 
534 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
536 _STLP_STD::pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
537  _InputIter1 __last1,
538  _InputIter2 __first2,
539  _BinaryPredicate __binary_pred) {
540  _STLP_FIX_LITERAL_BUG(__first2)
541  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
542  while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
543  ++__first1;
544  ++__first2;
545  }
546  return _STLP_STD::pair<_InputIter1, _InputIter2>(__first1, __first2);
547 }
548 
549 template <class _InputIter1, class _InputIter2>
551 bool equal(_InputIter1 __first1, _InputIter1 __last1,
552  _InputIter2 __first2) {
554  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
555  for ( ; __first1 != __last1; ++__first1, ++__first2)
556  if (!(*__first1 == *__first2))
557  return false;
558  return true;
559 }
560 
561 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
563 bool equal(_InputIter1 __first1, _InputIter1 __last1,
564  _InputIter2 __first2, _BinaryPredicate __binary_pred) {
565  _STLP_FIX_LITERAL_BUG(__first2)
566  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
567  for ( ; __first1 != __last1; ++__first1, ++__first2)
568  if (!__binary_pred(*__first1, *__first2))
569  return false;
570  return true;
571 }
572 
573 //--------------------------------------------------
574 // lexicographical_compare and lexicographical_compare_3way.
575 // (the latter is not part of the C++ standard.)
576 
577 template <class _InputIter1, class _InputIter2>
578 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
579  _InputIter2 __first2, _InputIter2 __last2);
580 
581 template <class _InputIter1, class _InputIter2, class _Compare>
582 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
583  _InputIter2 __first2, _InputIter2 __last2,
584  _Compare __comp);
585 
586 inline bool
587 lexicographical_compare(const unsigned char* __first1,
588  const unsigned char* __last1,
589  const unsigned char* __first2,
590  const unsigned char* __last2) {
591  const size_t __len1 = __last1 - __first1;
592  const size_t __len2 = __last2 - __first2;
593  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
594  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
595 
596  const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
597  return __result != 0 ? (__result < 0) : (__len1 < __len2);
598 }
599 
600 
601 #if !(CHAR_MAX == SCHAR_MAX)
602 inline bool lexicographical_compare(const char* __first1, const char* __last1,
603  const char* __first2, const char* __last2) {
604  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
605  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
606 
607  return lexicographical_compare((const unsigned char*) __first1,
608  (const unsigned char*) __last1,
609  (const unsigned char*) __first2,
610  (const unsigned char*) __last2);
611 }
612 #endif /* CHAR_MAX == SCHAR_MAX */
613 
615 
616 template <class _InputIter1, class _InputIter2>
617 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
618  _InputIter2 __first2, _InputIter2 __last2);
619 
620 inline int
621 __lexicographical_compare_3way(const unsigned char* __first1,
622  const unsigned char* __last1,
623  const unsigned char* __first2,
624  const unsigned char* __last2) {
625  const ptrdiff_t __len1 = __last1 - __first1;
626  const ptrdiff_t __len2 = __last2 - __first2;
627  const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
628  return __result != 0 ? __result
629  : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
630 }
631 
632 
633 #if !(CHAR_MAX == SCHAR_MAX)
634 inline int
635 __lexicographical_compare_3way(const char* __first1, const char* __last1,
636  const char* __first2, const char* __last2) {
637  return __lexicographical_compare_3way((const unsigned char*) __first1,
638  (const unsigned char*) __last1,
639  (const unsigned char*) __first2,
640  (const unsigned char*) __last2);
641 }
642 #endif
643 
645 
646 #if !defined (_STLP_NO_EXTENSIONS)
647 template <class _InputIter1, class _InputIter2>
648 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
649  _InputIter2 __first2, _InputIter2 __last2);
650 
651 #endif
652 
653 // count
654 template <class _InputIter, class _Tp>
656 count(_InputIter __first, _InputIter __last, const _Tp& __val) {
657  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
658  _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;
659  for ( ; __first != __last; ++__first)
660  if (*__first == __val)
661  ++__n;
662  return __n;
663 }
664 
665 // find and find_if. Note find may be expressed in terms of find_if if appropriate binder was available.
666 template <class _InputIter, class _Tp>
667 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val);
668 
669 template <class _InputIter, class _Predicate>
670 _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred);
671 
672 // search.
673 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
674 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
675  _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred __predicate);
676 
678 
679 // find_first_of
680 template <class _InputIter, class _ForwardIter>
681 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
682  _ForwardIter __first2, _ForwardIter __last2);
683 
684 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
685 _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
686  _ForwardIter __first2, _ForwardIter __last2,
687  _BinaryPredicate __comp);
688 
690 
691 template <class _ForwardIter1, class _ForwardIter2,
692  class _BinaryPredicate>
693 _ForwardIter1
694 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
695  _ForwardIter2 __first2, _ForwardIter2 __last2,
696  _BinaryPredicate __comp);
697 
698 // replace
699 template <class _ForwardIter, class _Tp>
701 replace(_ForwardIter __first, _ForwardIter __last,
702  const _Tp& __old_value, const _Tp& __new_value) {
703  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
704  for ( ; __first != __last; ++__first)
705  if (*__first == __old_value)
706  *__first = __new_value;
707 }
708 
710 
711 template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
712 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
713  const _Tp& __val, _Compare1 __comp1, _Compare2 __comp2, _Distance*);
714 
716 
718 
719 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
720 # include <stl/_algobase.c>
721 #endif
722 
723 #endif /* _STLP_INTERNAL_ALGOBASE_H */
724 
725 // Local Variables:
726 // mode:C++
727 // End:
728 
#define memmove(s1, s2, n)
Definition: mkisofs.h:881
_STLP_MOVE_TO_PRIV_NAMESPACE void __iter_swap_aux_aux(_ForwardIter1 &__i1, _ForwardIter2 &__i2, _Value *)
Definition: _algobase.h:100
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
_OKToSwap< _Tp1, _Tp2, _IsRef1, _IsRef2 > _IsOKToSwap(_Tp1 *, _Tp2 *, const _IsRef1 &, const _IsRef2 &)
Definition: type_traits.h:497
_InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred)
Definition: _algobase.c:214
#define random_access_iterator_tag
Definition: _abbrevs.h:28
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
_STLP_BEGIN_NAMESPACE void swap(_Tp &__a, _Tp &__b)
Definition: _algobase.h:81
GLuint GLuint GLsizei count
Definition: gl.h:1545
_STLP_INLINE_LOOP _InputIter _Predicate __pred
Definition: _algo.h:68
_STLP_MOVE_TO_PRIV_NAMESPACE _STLP_INLINE_LOOP _OutputIter __fill_n(_OutputIter __first, _Size __n, const _Tp &__val)
Definition: _algobase.h:478
_BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, _BidirectionalIter1 __last, _BidirectionalIter2 __result, const bidirectional_iterator_tag &, _Distance *)
Definition: _algobase.h:232
_STLP_MOVE_TO_PRIV_NAMESPACE _STLP_INLINE_LOOP _STLP_STD::pair< _InputIter, _OutputIter > __copy_n(_InputIter __first, _Size __count, _OutputIter __result, const input_iterator_tag &)
Definition: _algobase.h:377
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter1 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPredicate __comp)
Definition: _algobase.c:434
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare1 __comp1, _Compare2 __comp2, _Distance *)
Definition: _algobase.c:453
#define _STLP_ITERATOR_CATEGORY(_It, _Tp)
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
#define _STLP_DECLARE_COPY_TRIVIAL(_Tp)
Definition: _algobase.h:334
_STLP_INLINE_LOOP _STLP_STD::pair< _InputIter1, _InputIter2 > mismatch(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2)
Definition: _algobase.h:522
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred __predicate)
Definition: _algobase.c:227
#define _STLP_IS_REF_TYPE_REAL_REF(_It, _Tp)
_STLP_MOVE_TO_STD_NAMESPACE int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
Definition: _algobase.c:101
#define _STLP_LONG_LONG
Definition: _apcc.h:12
_STLP_MOVE_TO_PRIV_NAMESPACE int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
Definition: _algobase.c:78
_STLP_MOVE_TO_PRIV_NAMESPACE _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type &)
Definition: _algobase.h:299
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:449
_STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter) count(_InputIter __first
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_STLP_MOVE_TO_PRIV_NAMESPACE _OutputIter __copy(_InputIter __first, _InputIter __last, _OutputIter __result, const input_iterator_tag &, _Distance *)
Definition: _algobase.h:184
_STLP_MOVE_TO_STD_NAMESPACE pair< _InputIter, _OutputIter > copy_n(_InputIter __first, _Size __count, _OutputIter __result)
Definition: _algobase.h:399
#define _STLP_INLINE_LOOP
Definition: features.h:648
#define _STLP_VALUE_TYPE(_It, _Tp)
_STLP_INLINE_LOOP void replace(_ForwardIter __first, _ForwardIter __last, const _Tp &__old_value, const _Tp &__new_value)
Definition: _algobase.h:701
_STLP_MOVE_TO_PRIV_NAMESPACE _InputIter __find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2)
Definition: _algobase.c:339
_OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type &)
Definition: _algobase.h:312
#define _STLP_PRIV
Definition: _dm.h:70
_TrivialCopy< _Src, _Dst > _UseTrivialCopy(_Src *, _Dst *)
Definition: type_traits.h:501
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
Definition: _algobase.c:39
void * __copy_trivial_backward(const void *__first, const void *__last, void *__result)
Definition: _algobase.h:254
const _Tp &() max(const _Tp &__a, const _Tp &__b)
Definition: _algobase.h:141
_STLP_MOVE_TO_STD_NAMESPACE void fill_n(_OutputIter __first, _Size __n, const _Tp &__val)
Definition: _algobase.h:511
_STLP_INLINE_LOOP _InputIter __last
Definition: _algobase.h:656
_STLP_INLINE_LOOP bool equal(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2)
Definition: _algobase.h:551
#define long
Definition: qsort.c:33
void __iter_swap_aux(_ForwardIter1 &__i1, _ForwardIter2 &__i2, const __true_type &)
Definition: _algobase.h:107
#define _STLP_END_NAMESPACE
Definition: features.h:503
Definition: _pair.h:47
void * __copy_trivial(const void *__first, const void *__last, void *__result)
Definition: _algobase.h:222
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
_STLP_MOVE_TO_STD_NAMESPACE void iter_swap(_ForwardIter1 __i1, _ForwardIter2 __i2)
Definition: _algobase.h:120
#define _STLP_FIX_LITERAL_BUG(__x)
Definition: features.h:301
void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, const input_iterator_tag &, _Distance *)
Definition: _algobase.h:417
_Check_return_ _Ret_maybenull_ _In_ size_t _In_ size_t _Size
Definition: malloc.h:112
#define const
Definition: zconf.h:230
_InputIter find(_InputIter __first, _InputIter __last, const _Tp &__val)
Definition: _algobase.c:221
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
int _Value
Definition: setjmp.h:188
#define _STLP_DISTANCE_TYPE(_It, _Tp)
const _Tp &() min(const _Tp &__a, const _Tp &__b)
Definition: _algobase.h:139
#define memset(x, y, z)
Definition: compat.h:39
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter copy_backward(_InputIter __first, _InputIter __last, _OutputIter __result)
Definition: _algobase.h:328
_STLP_MOVE_TO_PRIV_NAMESPACE _STLP_INLINE_LOOP void __fill_fwd(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:411
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result)
Definition: _algobase.h:291
_OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type &)
Definition: _algobase.h:260
_OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type &)
Definition: _algobase.h:273
return __n
Definition: _algobase.h:662