- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_algobase.h

    00001 /*
    00002  *
    00003  * Copyright (c) 1994
    00004  * Hewlett-Packard Company
    00005  *
    00006  * Permission to use, copy, modify, distribute and sell this software
    00007  * and its documentation for any purpose is hereby granted without fee,
    00008  * provided that the above copyright notice appear in all copies and
    00009  * that both that copyright notice and this permission notice appear
    00010  * in supporting documentation.  Hewlett-Packard Company makes no
    00011  * representations about the suitability of this software for any
    00012  * purpose.  It is provided "as is" without express or implied warranty.
    00013  *
    00014  *
    00015  * Copyright (c) 1996-1998
    00016  * Silicon Graphics Computer Systems, Inc.
    00017  *
    00018  * Permission to use, copy, modify, distribute and sell this software
    00019  * and its documentation for any purpose is hereby granted without fee,
    00020  * provided that the above copyright notice appear in all copies and
    00021  * that both that copyright notice and this permission notice appear
    00022  * in supporting documentation.  Silicon Graphics makes no
    00023  * representations about the suitability of this software for any
    00024  * purpose.  It is provided "as is" without express or implied warranty.
    00025  */
    00026
    00027 /* NOTE: This is an internal header file, included by other STL headers.
    00028  *   You should not attempt to use it directly.
    00029  */
    00030
    00031
    00032 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
    00033 #define __SGI_STL_INTERNAL_ALGOBASE_H
    00034
    00035 #ifndef __STL_CONFIG_H
    00036 #include <stl_config.h>
    00037 #endif
    00038 #ifndef __SGI_STL_INTERNAL_RELOPS
    00039 #include <stl_relops.h>
    00040 #endif
    00041 #ifndef __SGI_STL_INTERNAL_PAIR_H
    00042 #include <stl_pair.h>
    00043 #endif
    00044 #ifndef __TYPE_TRAITS_H_
    00045 #include <type_traits.h>
    00046 #endif
    00047
    00048 #include <string.h>
    00049 #include <limits.h>
    00050 #include <stdlib.h>
    00051 #include <stddef.h>
    00052 #include <new.h>
    00053 #include <iostream>
    00054
    00055 #ifndef __SGI_STL_INTERNAL_ITERATOR_H
    00056 #include <stl_iterator.h>
    00057 #endif
    00058
    00059 __STL_BEGIN_NAMESPACE
    00060
    00061 // swap and iter_swap
    00062
    00063 template <class _ForwardIter1, class _ForwardIter2, class _Tp>
    00064 inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) {
    00065   _Tp __tmp = *__a;
    00066   *__a = *__b;
    00067   *__b = __tmp;
    00068 }
    00069
    00070 template <class _ForwardIter1, class _ForwardIter2>
    00071 inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {
    00072   __iter_swap(__a, __b, __VALUE_TYPE(__a));
    00073 }
    00074
    00075 template <class _Tp>
    00076 inline void swap(_Tp& __a, _Tp& __b) {
    00077   _Tp __tmp = __a;
    00078   __a = __b;
    00079   __b = __tmp;
    00080 }
    00081
    00082 //--------------------------------------------------
    00083 // min and max
    00084
    00085 #ifndef __BORLANDC__
    00086
    00087 #undef min
    00088 #undef max
    00089
    00090 template <class _Tp>
    00091 inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
    00092   return __b < __a ? __b : __a;
    00093 }
    00094
    00095 template <class _Tp>
    00096 inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
    00097   return  __a < __b ? __b : __a;
    00098 }
    00099
    00100 #endif /* __BORLANDC__ */
    00101
    00102 template <class _Tp, class _Compare>
    00103 inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
    00104   return __comp(__b, __a) ? __b : __a;
    00105 }
    00106
    00107 template <class _Tp, class _Compare>
    00108 inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
    00109   return __comp(__a, __b) ? __b : __a;
    00110 }
    00111
    00112 //--------------------------------------------------
    00113 // copy
    00114
    00115 // All of these auxiliary functions serve two purposes.  (1) Replace
    00116 // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
    00117 // because the input and output ranges are permitted to overlap.)
    00118 // (2) If we're using random access iterators, then write the loop as
    00119 // a for loop with an explicit count.  The auxiliary class __copy_dispatch
    00120 // is a workaround for compilers that don't support partial ordering of
    00121 // function templates.
    00122
    00123 template <class _InputIter, class _OutputIter, class _Distance>
    00124 inline _OutputIter __copy(_InputIter __first, _InputIter __last,
    00125                           _OutputIter __result,
    00126                           input_iterator_tag, _Distance*)
    00127 {
    00128   for ( ; __first != __last; ++__result, ++__first)
    00129     *__result = *__first;
    00130   return __result;
    00131 }
    00132
    00133 template <class _RandomAccessIter, class _OutputIter, class _Distance>
    00134 inline _OutputIter
    00135 __copy(_RandomAccessIter __first, _RandomAccessIter __last,
    00136        _OutputIter __result, random_access_iterator_tag, _Distance*)
    00137 {
    00138   for (_Distance __n = __last - __first; __n > 0; --__n) {
    00139     *__result = *__first;
    00140     ++__first;
    00141     ++__result;
    00142   }
    00143   return __result;
    00144 }
    00145
    00146 template <class _Tp>
    00147 inline _Tp*
    00148 __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    00149   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
    00150   return __result + (__last - __first);
    00151 }
    00152
    00153 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00154
    00155 template <class _InputIter, class _OutputIter, class _BoolType>
    00156 struct __copy_dispatch {
    00157   static _OutputIter copy(_InputIter __first, _InputIter __last,
    00158                           _OutputIter __result) {
    00159     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
    00160     typedef typename iterator_traits<_InputIter>::difference_type _Distance;
    00161     return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
    00162   }
    00163 };
    00164
    00165 template <class _Tp>
    00166 struct __copy_dispatch<_Tp*, _Tp*, __true_type>
    00167 {
    00168   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    00169     return __copy_trivial(__first, __last, __result);
    00170   }
    00171 };
    00172
    00173 template <class _Tp>
    00174 struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
    00175 {
    00176   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    00177     return __copy_trivial(__first, __last, __result);
    00178   }
    00179 };
    00180
    00181 template <class _InputIter, class _OutputIter>
    00182 inline _OutputIter copy(_InputIter __first, _InputIter __last,
    00183                         _OutputIter __result) {
    00184   typedef typename iterator_traits<_InputIter>::value_type _Tp;
    00185   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
    00186           _Trivial;
    00187   return __copy_dispatch<_InputIter, _OutputIter, _Trivial>
    00188     ::copy(__first, __last, __result);
    00189 }
    00190
    00191 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00192
    00193 template <class _InputIter, class _OutputIter>
    00194 inline _OutputIter copy(_InputIter __first, _InputIter __last,
    00195                         _OutputIter __result)
    00196 {
    00197   return __copy(__first, __last, __result,
    00198                 __ITERATOR_CATEGORY(__first),
    00199                 __DISTANCE_TYPE(__first));
    00200 }
    00201
    00202 inline char* copy(const char* __first, const char* __last, char* __result) {
    00203   memmove(__result, __first, __last - __first);
    00204   return __result + (__last - __first);
    00205 }
    00206
    00207 inline wchar_t* copy(const wchar_t* __first, const wchar_t* __last,
    00208                      wchar_t* __result) {
    00209   memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
    00210   return __result + (__last - __first);
    00211 }
    00212
    00213 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00214
    00215 //--------------------------------------------------
    00216 // copy_backward
    00217
    00218 template <class _BidirectionalIter1, class _BidirectionalIter2,
    00219           class _Distance>
    00220 inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
    00221                                            _BidirectionalIter1 __last,
    00222                                            _BidirectionalIter2 __result,
    00223                                            bidirectional_iterator_tag,
    00224                                            _Distance*)
    00225 {
    00226   while (__first != __last)
    00227     *--__result = *--__last;
    00228   return __result;
    00229 }
    00230
    00231 template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
    00232 inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,
    00233                                           _RandomAccessIter __last,
    00234                                           _BidirectionalIter __result,
    00235                                           random_access_iterator_tag,
    00236                                           _Distance*)
    00237 {
    00238   for (_Distance __n = __last - __first; __n > 0; --__n)
    00239     *--__result = *--__last;
    00240   return __result;
    00241 }
    00242
    00243 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00244
    00245 // This dispatch class is a workaround for compilers that do not
    00246 // have partial ordering of function templates.  All we're doing is
    00247 // creating a specialization so that we can turn a call to copy_backward
    00248 // into a memmove whenever possible.
    00249
    00250 template <class _BidirectionalIter1, class _BidirectionalIter2,
    00251           class _BoolType>
    00252 struct __copy_backward_dispatch
    00253 {
    00254   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category
    00255           _Cat;
    00256   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
    00257           _Distance;
    00258
    00259   static _BidirectionalIter2 copy(_BidirectionalIter1 __first,
    00260                                   _BidirectionalIter1 __last,
    00261                                   _BidirectionalIter2 __result) {
    00262     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
    00263   }
    00264 };
    00265
    00266 template <class _Tp>
    00267 struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
    00268 {
    00269   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    00270     const ptrdiff_t _Num = __last - __first;
    00271     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
    00272     return __result - _Num;
    00273   }
    00274 };
    00275
    00276 template <class _Tp>
    00277 struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
    00278 {
    00279   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    00280     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
    00281       ::copy(__first, __last, __result);
    00282   }
    00283 };
    00284
    00285 template <class _BI1, class _BI2>
    00286 inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
    00287   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
    00288                         ::has_trivial_assignment_operator
    00289           _Trivial;
    00290   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
    00291               ::copy(__first, __last, __result);
    00292 }
    00293
    00294 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00295
    00296 template <class _BI1, class _BI2>
    00297 inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
    00298   return __copy_backward(__first, __last, __result,
    00299                          __ITERATOR_CATEGORY(__first),
    00300                          __DISTANCE_TYPE(__first));
    00301 }
    00302
    00303 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00304
    00305 //--------------------------------------------------
    00306 // copy_n (not part of the C++ standard)
    00307
    00308 template <class _InputIter, class _Size, class _OutputIter>
    00309 pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
    00310                                        _OutputIter __result,
    00311                                        input_iterator_tag) {
    00312   for ( ; __count > 0; --__count) {
    00313     *__result = *__first;
    00314     ++__first;
    00315     ++__result;
    00316   }
    00317   return pair<_InputIter, _OutputIter>(__first, __result);
    00318 }
    00319
    00320 template <class _RAIter, class _Size, class _OutputIter>
    00321 inline pair<_RAIter, _OutputIter>
    00322 __copy_n(_RAIter __first, _Size __count,
    00323          _OutputIter __result,
    00324          random_access_iterator_tag) {
    00325   _RAIter __last = __first + __count;
    00326   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
    00327 }
    00328
    00329 template <class _InputIter, class _Size, class _OutputIter>
    00330 inline pair<_InputIter, _OutputIter>
    00331 __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
    00332   return __copy_n(__first, __count, __result,
    00333                   __ITERATOR_CATEGORY(__first));
    00334 }
    00335
    00336 template <class _InputIter, class _Size, class _OutputIter>
    00337 inline pair<_InputIter, _OutputIter>
    00338 copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
    00339   return __copy_n(__first, __count, __result);
    00340 }
    00341
    00342 //--------------------------------------------------
    00343 // fill and fill_n
    00344
    00345
    00346 template <class _ForwardIter, class _Tp>
    00347 void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) {
    00348   for ( ; __first != __last; ++__first)
    00349     *__first = __value;
    00350 }
    00351
    00352 template <class _OutputIter, class _Size, class _Tp>
    00353 _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
    00354   for ( ; __n > 0; --__n, ++__first)
    00355     *__first = __value;
    00356   return __first;
    00357 }
    00358
    00359 //--------------------------------------------------
    00360 // equal and mismatch
    00361
    00362 template <class _InputIter1, class _InputIter2>
    00363 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
    00364                                         _InputIter1 __last1,
    00365                                         _InputIter2 __first2) {
    00366   while (__first1 != __last1 && *__first1 == *__first2) {
    00367     ++__first1;
    00368     ++__first2;
    00369   }
    00370   return pair<_InputIter1, _InputIter2>(__first1, __first2);
    00371 }
    00372
    00373 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
    00374 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
    00375                                         _InputIter1 __last1,
    00376                                         _InputIter2 __first2,
    00377                                         _BinaryPredicate __binary_pred) {
    00378   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
    00379     ++__first1;
    00380     ++__first2;
    00381   }
    00382   return pair<_InputIter1, _InputIter2>(__first1, __first2);
    00383 }
    00384
    00385 template <class _InputIter1, class _InputIter2>
    00386 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
    00387                   _InputIter2 __first2) {
    00388   for ( ; __first1 != __last1; ++__first1, ++__first2)
    00389     if (*__first1 != *__first2)
    00390       return false;
    00391   return true;
    00392 }
    00393
    00394 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
    00395 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
    00396                   _InputIter2 __first2, _BinaryPredicate __binary_pred) {
    00397   for ( ; __first1 != __last1; ++__first1, ++__first2)
    00398     if (!__binary_pred(*__first1, *__first2))
    00399       return false;
    00400   return true;
    00401 }
    00402
    00403 //--------------------------------------------------
    00404 // lexicographical_compare and lexicographical_compare_3way.
    00405 // (the latter is not part of the C++ standard.)
    00406
    00407 template <class _InputIter1, class _InputIter2>
    00408 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
    00409                              _InputIter2 __first2, _InputIter2 __last2) {
    00410   for ( ; __first1 != __last1 && __first2 != __last2
    00411         ; ++__first1, ++__first2) {
    00412     if (*__first1 < *__first2)
    00413       return true;
    00414     if (*__first2 < *__first1)
    00415       return false;
    00416   }
    00417   return __first1 == __last1 && __first2 != __last2;
    00418 }
    00419
    00420 template <class _InputIter1, class _InputIter2, class _Compare>
    00421 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
    00422                              _InputIter2 __first2, _InputIter2 __last2,
    00423                              _Compare __comp) {
    00424   for ( ; __first1 != __last1 && __first2 != __last2
    00425         ; ++__first1, ++__first2) {
    00426     if (__comp(*__first1, *__first2))
    00427       return true;
    00428     if (__comp(*__first2, *__first1))
    00429       return false;
    00430   }
    00431   return __first1 == __last1 && __first2 != __last2;
    00432 }
    00433
    00434 inline bool
    00435 lexicographical_compare(const unsigned char* __first1,
    00436                         const unsigned char* __last1,
    00437                         const unsigned char* __first2,
    00438                         const unsigned char* __last2)
    00439 {
    00440   const size_t __len1 = __last1 - __first1;
    00441   const size_t __len2 = __last2 - __first2;
    00442   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
    00443   return __result != 0 ? __result < 0 : __len1 < __len2;
    00444 }
    00445
    00446 inline bool lexicographical_compare(const char* __first1, const char* __last1,
    00447                                     const char* __first2, const char* __last2)
    00448 {
    00449 #if CHAR_MAX == SCHAR_MAX
    00450   return lexicographical_compare((const signed char*) __first1,
    00451                                  (const signed char*) __last1,
    00452                                  (const signed char*) __first2,
    00453                                  (const signed char*) __last2);
    00454 #else /* CHAR_MAX == SCHAR_MAX */
    00455   return lexicographical_compare((const unsigned char*) __first1,
    00456                                  (const unsigned char*) __last1,
    00457                                  (const unsigned char*) __first2,
    00458                                  (const unsigned char*) __last2);
    00459 #endif /* CHAR_MAX == SCHAR_MAX */
    00460 }
    00461
    00462 template <class _InputIter1, class _InputIter2>
    00463 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
    00464                                    _InputIter2 __first2, _InputIter2 __last2)
    00465 {
    00466   while (__first1 != __last1 && __first2 != __last2) {
    00467     if (*__first1 < *__first2)
    00468       return -1;
    00469     if (*__first2 < *__first1)
    00470       return 1;
    00471     ++__first1;
    00472     ++__first2;
    00473   }
    00474   if (__first2 == __last2) {
    00475     return !(__first1 == __last1);
    00476   }
    00477   else {
    00478     return -1;
    00479   }
    00480 }
    00481
    00482 inline int
    00483 __lexicographical_compare_3way(const unsigned char* __first1,
    00484                                const unsigned char* __last1,
    00485                                const unsigned char* __first2,
    00486                                const unsigned char* __last2)
    00487 {
    00488   const ptrdiff_t __len1 = __last1 - __first1;
    00489   const ptrdiff_t __len2 = __last2 - __first2;
    00490   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
    00491   return __result != 0 ? __result
    00492                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
    00493 }
    00494
    00495 inline int
    00496 __lexicographical_compare_3way(const char* __first1, const char* __last1,
    00497                                const char* __first2, const char* __last2)
    00498 {
    00499 #if CHAR_MAX == SCHAR_MAX
    00500   return __lexicographical_compare_3way(
    00501                                 (const signed char*) __first1,
    00502                                 (const signed char*) __last1,
    00503                                 (const signed char*) __first2,
    00504                                 (const signed char*) __last2);
    00505 #else
    00506   return __lexicographical_compare_3way((const unsigned char*) __first1,
    00507                                         (const unsigned char*) __last1,
    00508                                         (const unsigned char*) __first2,
    00509                                         (const unsigned char*) __last2);
    00510 #endif
    00511 }
    00512
    00513 template <class _InputIter1, class _InputIter2>
    00514 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
    00515                                  _InputIter2 __first2, _InputIter2 __last2)
    00516 {
    00517   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
    00518 }
    00519
    00520 __STL_END_NAMESPACE
    00521
    00522 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
    00523
    00524 // Local Variables:
    00525 // mode:C++
    00526 // End: