4 * Hewlett-Packard Company
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
15 * Copyright (c) 1996-1998
16 * Silicon Graphics Computer Systems, Inc.
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
32 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
33 #define __SGI_STL_INTERNAL_ALGOBASE_H
35 #include <bits/c++config.h>
36 #ifndef __SGI_STL_INTERNAL_PAIR_H
37 #include <bits/stl_pair.h>
39 #ifndef _CPP_BITS_TYPE_TRAITS_H
40 #include <bits/type_traits.h>
42 #include <bits/std_cstring.h>
43 #include <bits/std_climits.h>
44 #include <bits/std_cstdlib.h>
45 #include <bits/std_cstddef.h>
48 #include <bits/std_iosfwd.h>
49 #include <bits/stl_iterator_base.h>
50 #include <bits/stl_iterator.h>
52 // We pick up concept_checks.h from stl_iterator_base.h.
59 template <class _ForwardIter1
, class _ForwardIter2
, class _Tp
>
60 inline void __iter_swap(_ForwardIter1 __a
, _ForwardIter2 __b
, _Tp
*) {
66 template <class _ForwardIter1
, class _ForwardIter2
>
67 inline void iter_swap(_ForwardIter1 __a
, _ForwardIter2 __b
) {
68 __STL_REQUIRES(_ForwardIter1
, _Mutable_ForwardIterator
);
69 __STL_REQUIRES(_ForwardIter2
, _Mutable_ForwardIterator
);
70 __STL_CONVERTIBLE(typename iterator_traits
<_ForwardIter1
>::value_type
,
71 typename iterator_traits
<_ForwardIter2
>::value_type
);
72 __STL_CONVERTIBLE(typename iterator_traits
<_ForwardIter2
>::value_type
,
73 typename iterator_traits
<_ForwardIter1
>::value_type
);
74 __iter_swap(__a
, __b
, __VALUE_TYPE(__a
));
78 inline void swap(_Tp
& __a
, _Tp
& __b
) {
79 __STL_REQUIRES(_Tp
, _Assignable
);
85 //--------------------------------------------------
92 inline const _Tp
& min(const _Tp
& __a
, const _Tp
& __b
) {
93 __STL_REQUIRES(_Tp
, _LessThanComparable
);
94 //return __b < __a ? __b : __a;
95 if (__b
< __a
) return __b
; return __a
;
99 inline const _Tp
& max(const _Tp
& __a
, const _Tp
& __b
) {
100 __STL_REQUIRES(_Tp
, _LessThanComparable
);
101 //return __a < __b ? __b : __a;
102 if (__a
< __b
) return __b
; return __a
;
105 template <class _Tp
, class _Compare
>
106 inline const _Tp
& min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
) {
107 //return __comp(__b, __a) ? __b : __a;
108 if (__comp(__b
, __a
)) return __b
; return __a
;
111 template <class _Tp
, class _Compare
>
112 inline const _Tp
& max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
) {
113 //return __comp(__a, __b) ? __b : __a;
114 if (__comp(__a
, __b
)) return __b
; return __a
;
117 //--------------------------------------------------
120 // All of these auxiliary functions serve two purposes. (1) Replace
121 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
122 // because the input and output ranges are permitted to overlap.)
123 // (2) If we're using random access iterators, then write the loop as
124 // a for loop with an explicit count.
126 template <class _InputIter
, class _OutputIter
, class _Distance
>
127 inline _OutputIter
__copy(_InputIter __first
, _InputIter __last
,
128 _OutputIter __result
,
129 input_iterator_tag
, _Distance
*)
131 for ( ; __first
!= __last
; ++__result
, ++__first
)
132 *__result
= *__first
;
136 template <class _RandomAccessIter
, class _OutputIter
, class _Distance
>
138 __copy(_RandomAccessIter __first
, _RandomAccessIter __last
,
139 _OutputIter __result
, random_access_iterator_tag
, _Distance
*)
141 for (_Distance __n
= __last
- __first
; __n
> 0; --__n
) {
142 *__result
= *__first
;
151 __copy_trivial(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
152 memmove(__result
, __first
, sizeof(_Tp
) * (__last
- __first
));
153 return __result
+ (__last
- __first
);
157 template <class _InputIter
, class _OutputIter
>
158 inline _OutputIter
__copy_aux2(_InputIter __first
, _InputIter __last
,
159 _OutputIter __result
, __false_type
) {
160 return __copy(__first
, __last
, __result
,
161 __ITERATOR_CATEGORY(__first
),
162 __DISTANCE_TYPE(__first
));
165 template <class _InputIter
, class _OutputIter
>
166 inline _OutputIter
__copy_aux2(_InputIter __first
, _InputIter __last
,
167 _OutputIter __result
, __true_type
) {
168 return __copy(__first
, __last
, __result
,
169 __ITERATOR_CATEGORY(__first
),
170 __DISTANCE_TYPE(__first
));
176 inline _Tp
* __copy_aux2(_Tp
* __first
, _Tp
* __last
, _Tp
* __result
,
178 return __copy_trivial(__first
, __last
, __result
);
181 #endif /* __USLC__ */
184 inline _Tp
* __copy_aux2(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
,
186 return __copy_trivial(__first
, __last
, __result
);
190 template <class _InputIter
, class _OutputIter
, class _Tp
>
191 inline _OutputIter
__copy_aux(_InputIter __first
, _InputIter __last
,
192 _OutputIter __result
, _Tp
*) {
193 typedef typename __type_traits
<_Tp
>::has_trivial_assignment_operator
195 return __copy_aux2(__first
, __last
, __result
, _Trivial());
198 template<typename _InputIter
, typename _OutputIter
>
199 inline _OutputIter
__copy_ni2(_InputIter __first
, _InputIter __last
,
200 _OutputIter __result
, __true_type
) {
201 return _OutputIter(__copy_aux(__first
, __last
, __result
.base(),
202 __VALUE_TYPE(__first
)));
205 template<typename _InputIter
, typename _OutputIter
>
206 inline _OutputIter
__copy_ni2(_InputIter __first
, _InputIter __last
,
207 _OutputIter __result
, __false_type
) {
208 return __copy_aux(__first
, __last
, __result
, __VALUE_TYPE(__first
));
211 template<typename _InputIter
, typename _OutputIter
>
212 inline _OutputIter
__copy_ni1(_InputIter __first
, _InputIter __last
,
213 _OutputIter __result
, __true_type
) {
214 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
215 return __copy_ni2(__first
.base(), __last
.base(), __result
, __Normal());
218 template<typename _InputIter
, typename _OutputIter
>
219 inline _OutputIter
__copy_ni1(_InputIter __first
, _InputIter __last
,
220 _OutputIter __result
, __false_type
) {
221 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
222 return __copy_ni2(__first
, __last
, __result
, __Normal());
225 template <class _InputIter
, class _OutputIter
>
226 inline _OutputIter
copy(_InputIter __first
, _InputIter __last
,
227 _OutputIter __result
) {
228 __STL_REQUIRES(_InputIter
, _InputIterator
);
229 __STL_REQUIRES(_OutputIter
, _OutputIterator
);
230 typedef typename _Is_normal_iterator
<_InputIter
>::_Normal __Normal
;
231 return __copy_ni1(__first
, __last
, __result
, __Normal());
234 //--------------------------------------------------
237 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
239 inline _BidirectionalIter2
__copy_backward(_BidirectionalIter1 __first
,
240 _BidirectionalIter1 __last
,
241 _BidirectionalIter2 __result
,
242 bidirectional_iterator_tag
,
245 while (__first
!= __last
)
246 *--__result
= *--__last
;
250 template <class _RandomAccessIter
, class _BidirectionalIter
, class _Distance
>
251 inline _BidirectionalIter
__copy_backward(_RandomAccessIter __first
,
252 _RandomAccessIter __last
,
253 _BidirectionalIter __result
,
254 random_access_iterator_tag
,
257 for (_Distance __n
= __last
- __first
; __n
> 0; --__n
)
258 *--__result
= *--__last
;
263 // This dispatch class is a workaround for compilers that do not
264 // have partial ordering of function templates. All we're doing is
265 // creating a specialization so that we can turn a call to copy_backward
266 // into a memmove whenever possible.
268 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
270 struct __copy_backward_dispatch
272 typedef typename iterator_traits
<_BidirectionalIter1
>::iterator_category
274 typedef typename iterator_traits
<_BidirectionalIter1
>::difference_type
277 static _BidirectionalIter2
copy(_BidirectionalIter1 __first
,
278 _BidirectionalIter1 __last
,
279 _BidirectionalIter2 __result
) {
280 return __copy_backward(__first
, __last
, __result
, _Cat(), (_Distance
*) 0);
285 struct __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
287 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
288 const ptrdiff_t _Num
= __last
- __first
;
289 memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
290 return __result
- _Num
;
295 struct __copy_backward_dispatch
<const _Tp
*, _Tp
*, __true_type
>
297 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
298 return __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
299 ::copy(__first
, __last
, __result
);
303 template <class _BI1
, class _BI2
>
304 inline _BI2
__copy_backward_aux(_BI1 __first
, _BI1 __last
, _BI2 __result
) {
305 typedef typename __type_traits
<typename iterator_traits
<_BI2
>::value_type
>
306 ::has_trivial_assignment_operator
308 return __copy_backward_dispatch
<_BI1
, _BI2
, _Trivial
>
309 ::copy(__first
, __last
, __result
);
312 template <typename _BI1
, typename _BI2
>
313 inline _BI2
__copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
314 _BI2 __result
, __true_type
) {
315 return _BI2(__copy_backward_aux(__first
, __last
, __result
.base()));
318 template <typename _BI1
, typename _BI2
>
319 inline _BI2
__copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
320 _BI2 __result
, __false_type
){
321 return __copy_backward_aux(__first
, __last
, __result
);
324 template <typename _BI1
, typename _BI2
>
325 inline _BI2
__copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
326 _BI2 __result
, __true_type
) {
327 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
328 return __copy_backward_output_normal_iterator(__first
.base(), __last
.base(),
329 __result
, __Normal());
332 template <typename _BI1
, typename _BI2
>
333 inline _BI2
__copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
334 _BI2 __result
, __false_type
) {
335 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
336 return __copy_backward_output_normal_iterator(__first
, __last
, __result
,
340 template <typename _BI1
, typename _BI2
>
341 inline _BI2
copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
) {
342 __STL_REQUIRES(_BI1
, _BidirectionalIterator
);
343 __STL_REQUIRES(_BI2
, _Mutable_BidirectionalIterator
);
344 __STL_CONVERTIBLE(typename iterator_traits
<_BI1
>::value_type
,
345 typename iterator_traits
<_BI2
>::value_type
);
346 typedef typename _Is_normal_iterator
<_BI1
>::_Normal __Normal
;
347 return __copy_backward_input_normal_iterator(__first
, __last
, __result
,
351 //--------------------------------------------------
352 // copy_n (not part of the C++ standard)
354 template <class _InputIter
, class _Size
, class _OutputIter
>
355 pair
<_InputIter
, _OutputIter
> __copy_n(_InputIter __first
, _Size __count
,
356 _OutputIter __result
,
357 input_iterator_tag
) {
358 for ( ; __count
> 0; --__count
) {
359 *__result
= *__first
;
363 return pair
<_InputIter
, _OutputIter
>(__first
, __result
);
366 template <class _RAIter
, class _Size
, class _OutputIter
>
367 inline pair
<_RAIter
, _OutputIter
>
368 __copy_n(_RAIter __first
, _Size __count
,
369 _OutputIter __result
,
370 random_access_iterator_tag
) {
371 _RAIter __last
= __first
+ __count
;
372 return pair
<_RAIter
, _OutputIter
>(__last
, copy(__first
, __last
, __result
));
375 template <class _InputIter
, class _Size
, class _OutputIter
>
376 inline pair
<_InputIter
, _OutputIter
>
377 __copy_n(_InputIter __first
, _Size __count
, _OutputIter __result
) {
378 return __copy_n(__first
, __count
, __result
,
379 __ITERATOR_CATEGORY(__first
));
382 template <class _InputIter
, class _Size
, class _OutputIter
>
383 inline pair
<_InputIter
, _OutputIter
>
384 copy_n(_InputIter __first
, _Size __count
, _OutputIter __result
) {
385 __STL_REQUIRES(_InputIter
, _InputIterator
);
386 __STL_REQUIRES(_OutputIter
, _OutputIterator
);
387 return __copy_n(__first
, __count
, __result
);
390 //--------------------------------------------------
394 template <class _ForwardIter
, class _Tp
>
395 void fill(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __value
) {
396 __STL_REQUIRES(_ForwardIter
, _Mutable_ForwardIterator
);
397 for ( ; __first
!= __last
; ++__first
)
401 template <class _OutputIter
, class _Size
, class _Tp
>
402 _OutputIter
fill_n(_OutputIter __first
, _Size __n
, const _Tp
& __value
) {
403 __STL_REQUIRES(_OutputIter
, _OutputIterator
);
404 for ( ; __n
> 0; --__n
, ++__first
)
409 // Specialization: for one-byte types we can use memset.
411 inline void fill(unsigned char* __first
, unsigned char* __last
,
412 const unsigned char& __c
) {
413 unsigned char __tmp
= __c
;
414 memset(__first
, __tmp
, __last
- __first
);
417 inline void fill(signed char* __first
, signed char* __last
,
418 const signed char& __c
) {
419 signed char __tmp
= __c
;
420 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
423 inline void fill(char* __first
, char* __last
, const char& __c
) {
425 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
428 template <class _Size
>
429 inline unsigned char* fill_n(unsigned char* __first
, _Size __n
,
430 const unsigned char& __c
) {
431 fill(__first
, __first
+ __n
, __c
);
432 return __first
+ __n
;
435 template <class _Size
>
436 inline signed char* fill_n(char* __first
, _Size __n
,
437 const signed char& __c
) {
438 fill(__first
, __first
+ __n
, __c
);
439 return __first
+ __n
;
442 template <class _Size
>
443 inline char* fill_n(char* __first
, _Size __n
, const char& __c
) {
444 fill(__first
, __first
+ __n
, __c
);
445 return __first
+ __n
;
449 //--------------------------------------------------
450 // equal and mismatch
452 template <class _InputIter1
, class _InputIter2
>
453 pair
<_InputIter1
, _InputIter2
> mismatch(_InputIter1 __first1
,
455 _InputIter2 __first2
) {
456 __STL_REQUIRES(_InputIter1
, _InputIterator
);
457 __STL_REQUIRES(_InputIter2
, _InputIterator
);
458 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
459 _EqualityComparable
);
460 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
461 _EqualityComparable
);
462 while (__first1
!= __last1
&& *__first1
== *__first2
) {
466 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
469 template <class _InputIter1
, class _InputIter2
, class _BinaryPredicate
>
470 pair
<_InputIter1
, _InputIter2
> mismatch(_InputIter1 __first1
,
472 _InputIter2 __first2
,
473 _BinaryPredicate __binary_pred
) {
474 __STL_REQUIRES(_InputIter1
, _InputIterator
);
475 __STL_REQUIRES(_InputIter2
, _InputIterator
);
476 while (__first1
!= __last1
&& __binary_pred(*__first1
, *__first2
)) {
480 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
483 template <class _InputIter1
, class _InputIter2
>
484 inline bool equal(_InputIter1 __first1
, _InputIter1 __last1
,
485 _InputIter2 __first2
) {
486 __STL_REQUIRES(_InputIter1
, _InputIterator
);
487 __STL_REQUIRES(_InputIter2
, _InputIterator
);
488 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
489 _EqualityComparable
);
490 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
491 _EqualityComparable
);
492 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
493 if (*__first1
!= *__first2
)
498 template <class _InputIter1
, class _InputIter2
, class _BinaryPredicate
>
499 inline bool equal(_InputIter1 __first1
, _InputIter1 __last1
,
500 _InputIter2 __first2
, _BinaryPredicate __binary_pred
) {
501 __STL_REQUIRES(_InputIter1
, _InputIterator
);
502 __STL_REQUIRES(_InputIter2
, _InputIterator
);
503 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
504 if (!__binary_pred(*__first1
, *__first2
))
509 //--------------------------------------------------
510 // lexicographical_compare and lexicographical_compare_3way.
511 // (the latter is not part of the C++ standard.)
513 template <class _InputIter1
, class _InputIter2
>
514 bool lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
515 _InputIter2 __first2
, _InputIter2 __last2
) {
516 __STL_REQUIRES(_InputIter1
, _InputIterator
);
517 __STL_REQUIRES(_InputIter2
, _InputIterator
);
518 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
519 _LessThanComparable
);
520 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
521 _LessThanComparable
);
522 for ( ; __first1
!= __last1
&& __first2
!= __last2
523 ; ++__first1
, ++__first2
) {
524 if (*__first1
< *__first2
)
526 if (*__first2
< *__first1
)
529 return __first1
== __last1
&& __first2
!= __last2
;
532 template <class _InputIter1
, class _InputIter2
, class _Compare
>
533 bool lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
534 _InputIter2 __first2
, _InputIter2 __last2
,
536 __STL_REQUIRES(_InputIter1
, _InputIterator
);
537 __STL_REQUIRES(_InputIter2
, _InputIterator
);
538 for ( ; __first1
!= __last1
&& __first2
!= __last2
539 ; ++__first1
, ++__first2
) {
540 if (__comp(*__first1
, *__first2
))
542 if (__comp(*__first2
, *__first1
))
545 return __first1
== __last1
&& __first2
!= __last2
;
549 lexicographical_compare(const unsigned char* __first1
,
550 const unsigned char* __last1
,
551 const unsigned char* __first2
,
552 const unsigned char* __last2
)
554 const size_t __len1
= __last1
- __first1
;
555 const size_t __len2
= __last2
- __first2
;
556 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
557 return __result
!= 0 ? __result
< 0 : __len1
< __len2
;
560 inline bool lexicographical_compare(const char* __first1
, const char* __last1
,
561 const char* __first2
, const char* __last2
)
563 #if CHAR_MAX == SCHAR_MAX
564 return lexicographical_compare((const signed char*) __first1
,
565 (const signed char*) __last1
,
566 (const signed char*) __first2
,
567 (const signed char*) __last2
);
568 #else /* CHAR_MAX == SCHAR_MAX */
569 return lexicographical_compare((const unsigned char*) __first1
,
570 (const unsigned char*) __last1
,
571 (const unsigned char*) __first2
,
572 (const unsigned char*) __last2
);
573 #endif /* CHAR_MAX == SCHAR_MAX */
576 template <class _InputIter1
, class _InputIter2
>
577 int __lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
578 _InputIter2 __first2
, _InputIter2 __last2
)
580 while (__first1
!= __last1
&& __first2
!= __last2
) {
581 if (*__first1
< *__first2
)
583 if (*__first2
< *__first1
)
588 if (__first2
== __last2
) {
589 return !(__first1
== __last1
);
597 __lexicographical_compare_3way(const unsigned char* __first1
,
598 const unsigned char* __last1
,
599 const unsigned char* __first2
,
600 const unsigned char* __last2
)
602 const ptrdiff_t __len1
= __last1
- __first1
;
603 const ptrdiff_t __len2
= __last2
- __first2
;
604 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
605 return __result
!= 0 ? __result
606 : (__len1
== __len2
? 0 : (__len1
< __len2
? -1 : 1));
610 __lexicographical_compare_3way(const char* __first1
, const char* __last1
,
611 const char* __first2
, const char* __last2
)
613 #if CHAR_MAX == SCHAR_MAX
614 return __lexicographical_compare_3way(
615 (const signed char*) __first1
,
616 (const signed char*) __last1
,
617 (const signed char*) __first2
,
618 (const signed char*) __last2
);
620 return __lexicographical_compare_3way((const unsigned char*) __first1
,
621 (const unsigned char*) __last1
,
622 (const unsigned char*) __first2
,
623 (const unsigned char*) __last2
);
627 template <class _InputIter1
, class _InputIter2
>
628 int lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
629 _InputIter2 __first2
, _InputIter2 __last2
)
631 __STL_REQUIRES(_InputIter1
, _InputIterator
);
632 __STL_REQUIRES(_InputIter2
, _InputIterator
);
633 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
634 _LessThanComparable
);
635 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
636 _LessThanComparable
);
637 return __lexicographical_compare_3way(__first1
, __last1
, __first2
, __last2
);
642 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */