headers/cpp/stl_algobase.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   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.
  13  *
  14  *
  15  * Copyright (c) 1996-1998
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  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.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31
  32 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
  33 #define __SGI_STL_INTERNAL_ALGOBASE_H
  34
  35 #ifndef __STL_CONFIG_H
  36 #include <stl_config.h>
  37 #endif
  38 #ifndef __SGI_STL_INTERNAL_RELOPS
  39 #include <stl_relops.h>
  40 #endif
  41 #ifndef __SGI_STL_INTERNAL_PAIR_H
  42 #include <stl_pair.h>
  43 #endif
  44 #ifndef __TYPE_TRAITS_H_
  45 #include <type_traits.h>
  46 #endif
  47
  48 #include <string.h>
  49 #include <limits.h>
  50 #include <stdlib.h>
  51 #include <stddef.h>
  52 #include <new.h>
  53 #include <iostream.h>
  54
  55 #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  56 #include <stl_iterator.h>
  57 #endif
  58
  59 __STL_BEGIN_NAMESPACE
  60
  61 // swap and iter_swap
  62
  63 template <class _ForwardIter1, class _ForwardIter2, class _Tp>
  64 inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) {
  65   _Tp __tmp = *__a;
  66   *__a = *__b;
  67   *__b = __tmp;
  68 }
  69
  70 template <class _ForwardIter1, class _ForwardIter2>
  71 inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {
  72   __iter_swap(__a, __b, __VALUE_TYPE(__a));
  73 }
  74
  75 template <class _Tp>
  76 inline void swap(_Tp& __a, _Tp& __b) {
  77   _Tp __tmp = __a;
  78   __a = __b;
  79   __b = __tmp;
  80 }
  81
  82 //--------------------------------------------------
  83 // min and max
  84
  85 #ifndef __BORLANDC__
  86
  87 #undef min
  88 #undef max
  89
  90 template <class _Tp>
  91 inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
  92   return __b < __a ? __b : __a;
  93 }
  94
  95 template <class _Tp>
  96 inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
  97   return  __a < __b ? __b : __a;
  98 }
  99
 100 #endif /* __BORLANDC__ */
 101
 102 template <class _Tp, class _Compare>
 103 inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
 104   return __comp(__b, __a) ? __b : __a;
 105 }
 106
 107 template <class _Tp, class _Compare>
 108 inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
 109   return __comp(__a, __b) ? __b : __a;
 110 }
 111
 112 //--------------------------------------------------
 113 // copy
 114
 115 // All of these auxiliary functions serve two purposes.  (1) Replace
 116 // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
 117 // because the input and output ranges are permitted to overlap.)
 118 // (2) If we're using random access iterators, then write the loop as
 119 // a for loop with an explicit count.  The auxiliary class __copy_dispatch
 120 // is a workaround for compilers that don't support partial ordering of
 121 // function templates.
 122
 123 template <class _InputIter, class _OutputIter, class _Distance>
 124 inline _OutputIter __copy(_InputIter __first, _InputIter __last,
 125                           _OutputIter __result,
 126                           input_iterator_tag, _Distance*)
 127 {
 128   for ( ; __first != __last; ++__result, ++__first)
 129     *__result = *__first;
 130   return __result;
 131 }
 132
 133 template <class _RandomAccessIter, class _OutputIter, class _Distance>
 134 inline _OutputIter
 135 __copy(_RandomAccessIter __first, _RandomAccessIter __last,
 136        _OutputIter __result, random_access_iterator_tag, _Distance*)
 137 {
 138   for (_Distance __n = __last - __first; __n > 0; --__n) {
 139     *__result = *__first;
 140     ++__first;
 141     ++__result;
 142   }
 143   return __result;
 144 }
 145
 146 template <class _Tp>
 147 inline _Tp*
 148 __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) {
 149   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
 150   return __result + (__last - __first);
 151 }
 152
 153 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 154
 155 template <class _InputIter, class _OutputIter, class _BoolType>
 156 struct __copy_dispatch {
 157   static _OutputIter copy(_InputIter __first, _InputIter __last,
 158                           _OutputIter __result) {
 159     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
 160     typedef typename iterator_traits<_InputIter>::difference_type _Distance;
 161     return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
 162   }
 163 };
 164
 165 template <class _Tp>
 166 struct __copy_dispatch<_Tp*, _Tp*, __true_type>
 167 {
 168   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
 169     return __copy_trivial(__first, __last, __result);
 170   }
 171 };
 172
 173 template <class _Tp>
 174 struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
 175 {
 176   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
 177     return __copy_trivial(__first, __last, __result);
 178   }
 179 };
 180
 181 template <class _InputIter, class _OutputIter>
 182 inline _OutputIter copy(_InputIter __first, _InputIter __last,
 183                         _OutputIter __result) {
 184   typedef typename iterator_traits<_InputIter>::value_type _Tp;
 185   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
 186           _Trivial;
 187   return __copy_dispatch<_InputIter, _OutputIter, _Trivial>
 188     ::copy(__first, __last, __result);
 189 }
 190
 191 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 192
 193 template <class _InputIter, class _OutputIter>
 194 inline _OutputIter copy(_InputIter __first, _InputIter __last,
 195                         _OutputIter __result)
 196 {
 197   return __copy(__first, __last, __result,
 198                 __ITERATOR_CATEGORY(__first),
 199                 __DISTANCE_TYPE(__first));
 200 }
 201
 202 inline char* copy(const char* __first, const char* __last, char* __result) {
 203   memmove(__result, __first, __last - __first);
 204   return __result + (__last - __first);
 205 }
 206
 207 inline wchar_t* copy(const wchar_t* __first, const wchar_t* __last,
 208                      wchar_t* __result) {
 209   memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
 210   return __result + (__last - __first);
 211 }
 212
 213 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 214
 215 //--------------------------------------------------
 216 // copy_backward
 217
 218 template <class _BidirectionalIter1, class _BidirectionalIter2,
 219           class _Distance>
 220 inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
 221                                            _BidirectionalIter1 __last,
 222                                            _BidirectionalIter2 __result,
 223                                            bidirectional_iterator_tag,
 224                                            _Distance*)
 225 {
 226   while (__first != __last)
 227     *--__result = *--__last;
 228   return __result;
 229 }
 230
 231 template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
 232 inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,
 233                                           _RandomAccessIter __last,
 234                                           _BidirectionalIter __result,
 235                                           random_access_iterator_tag,
 236                                           _Distance*)
 237 {
 238   for (_Distance __n = __last - __first; __n > 0; --__n)
 239     *--__result = *--__last;
 240   return __result;
 241 }
 242
 243 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 244
 245 // This dispatch class is a workaround for compilers that do not
 246 // have partial ordering of function templates.  All we're doing is
 247 // creating a specialization so that we can turn a call to copy_backward
 248 // into a memmove whenever possible.
 249
 250 template <class _BidirectionalIter1, class _BidirectionalIter2,
 251           class _BoolType>
 252 struct __copy_backward_dispatch
 253 {
 254   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category
 255           _Cat;
 256   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
 257           _Distance;
 258
 259   static _BidirectionalIter2 copy(_BidirectionalIter1 __first,
 260                                   _BidirectionalIter1 __last,
 261                                   _BidirectionalIter2 __result) {
 262     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
 263   }
 264 };
 265
 266 template <class _Tp>
 267 struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
 268 {
 269   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
 270     const ptrdiff_t _Num = __last - __first;
 271     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
 272     return __result - _Num;
 273   }
 274 };
 275
 276 template <class _Tp>
 277 struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
 278 {
 279   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
 280     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
 281       ::copy(__first, __last, __result);
 282   }
 283 };
 284
 285 template <class _BI1, class _BI2>
 286 inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
 287   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
 288                         ::has_trivial_assignment_operator
 289           _Trivial;
 290   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
 291               ::copy(__first, __last, __result);
 292 }
 293
 294 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 295
 296 template <class _BI1, class _BI2>
 297 inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
 298   return __copy_backward(__first, __last, __result,
 299                          __ITERATOR_CATEGORY(__first),
 300                          __DISTANCE_TYPE(__first));
 301 }
 302
 303 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 304
 305 //--------------------------------------------------
 306 // copy_n (not part of the C++ standard)
 307
 308 template <class _InputIter, class _Size, class _OutputIter>
 309 pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
 310                                        _OutputIter __result,
 311                                        input_iterator_tag) {
 312   for ( ; __count > 0; --__count) {
 313     *__result = *__first;
 314     ++__first;
 315     ++__result;
 316   }
 317   return pair<_InputIter, _OutputIter>(__first, __result);
 318 }
 319
 320 template <class _RAIter, class _Size, class _OutputIter>
 321 inline pair<_RAIter, _OutputIter>
 322 __copy_n(_RAIter __first, _Size __count,
 323          _OutputIter __result,
 324          random_access_iterator_tag) {
 325   _RAIter __last = __first + __count;
 326   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
 327 }
 328
 329 template <class _InputIter, class _Size, class _OutputIter>
 330 inline pair<_InputIter, _OutputIter>
 331 __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
 332   return __copy_n(__first, __count, __result,
 333                   __ITERATOR_CATEGORY(__first));
 334 }
 335
 336 template <class _InputIter, class _Size, class _OutputIter>
 337 inline pair<_InputIter, _OutputIter>
 338 copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
 339   return __copy_n(__first, __count, __result);
 340 }
 341
 342 //--------------------------------------------------
 343 // fill and fill_n
 344
 345
 346 template <class _ForwardIter, class _Tp>
 347 void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) {
 348   for ( ; __first != __last; ++__first)
 349     *__first = __value;
 350 }
 351
 352 template <class _OutputIter, class _Size, class _Tp>
 353 _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
 354   for ( ; __n > 0; --__n, ++__first)
 355     *__first = __value;
 356   return __first;
 357 }
 358
 359 //--------------------------------------------------
 360 // equal and mismatch
 361
 362 template <class _InputIter1, class _InputIter2>
 363 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
 364                                         _InputIter1 __last1,
 365                                         _InputIter2 __first2) {
 366   while (__first1 != __last1 && *__first1 == *__first2) {
 367     ++__first1;
 368     ++__first2;
 369   }
 370   return pair<_InputIter1, _InputIter2>(__first1, __first2);
 371 }
 372
 373 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
 374 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
 375                                         _InputIter1 __last1,
 376                                         _InputIter2 __first2,
 377                                         _BinaryPredicate __binary_pred) {
 378   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
 379     ++__first1;
 380     ++__first2;
 381   }
 382   return pair<_InputIter1, _InputIter2>(__first1, __first2);
 383 }
 384
 385 template <class _InputIter1, class _InputIter2>
 386 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
 387                   _InputIter2 __first2) {
 388   for ( ; __first1 != __last1; ++__first1, ++__first2)
 389     if (*__first1 != *__first2)
 390       return false;
 391   return true;
 392 }
 393
 394 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
 395 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
 396                   _InputIter2 __first2, _BinaryPredicate __binary_pred) {
 397   for ( ; __first1 != __last1; ++__first1, ++__first2)
 398     if (!__binary_pred(*__first1, *__first2))
 399       return false;
 400   return true;
 401 }
 402
 403 //--------------------------------------------------
 404 // lexicographical_compare and lexicographical_compare_3way.
 405 // (the latter is not part of the C++ standard.)
 406
 407 template <class _InputIter1, class _InputIter2>
 408 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
 409                              _InputIter2 __first2, _InputIter2 __last2) {
 410   for ( ; __first1 != __last1 && __first2 != __last2
 411         ; ++__first1, ++__first2) {
 412     if (*__first1 < *__first2)
 413       return true;
 414     if (*__first2 < *__first1)
 415       return false;
 416   }
 417   return __first1 == __last1 && __first2 != __last2;
 418 }
 419
 420 template <class _InputIter1, class _InputIter2, class _Compare>
 421 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
 422                              _InputIter2 __first2, _InputIter2 __last2,
 423                              _Compare __comp) {
 424   for ( ; __first1 != __last1 && __first2 != __last2
 425         ; ++__first1, ++__first2) {
 426     if (__comp(*__first1, *__first2))
 427       return true;
 428     if (__comp(*__first2, *__first1))
 429       return false;
 430   }
 431   return __first1 == __last1 && __first2 != __last2;
 432 }
 433
 434 inline bool
 435 lexicographical_compare(const unsigned char* __first1,
 436                         const unsigned char* __last1,
 437                         const unsigned char* __first2,
 438                         const unsigned char* __last2)
 439 {
 440   const size_t __len1 = __last1 - __first1;
 441   const size_t __len2 = __last2 - __first2;
 442   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
 443   return __result != 0 ? __result < 0 : __len1 < __len2;
 444 }
 445
 446 inline bool lexicographical_compare(const char* __first1, const char* __last1,
 447                                     const char* __first2, const char* __last2)
 448 {
 449 #if CHAR_MAX == SCHAR_MAX
 450   return lexicographical_compare((const signed char*) __first1,
 451                                  (const signed char*) __last1,
 452                                  (const signed char*) __first2,
 453                                  (const signed char*) __last2);
 454 #else /* CHAR_MAX == SCHAR_MAX */
 455   return lexicographical_compare((const unsigned char*) __first1,
 456                                  (const unsigned char*) __last1,
 457                                  (const unsigned char*) __first2,
 458                                  (const unsigned char*) __last2);
 459 #endif /* CHAR_MAX == SCHAR_MAX */
 460 }
 461
 462 template <class _InputIter1, class _InputIter2>
 463 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 464                                    _InputIter2 __first2, _InputIter2 __last2)
 465 {
 466   while (__first1 != __last1 && __first2 != __last2) {
 467     if (*__first1 < *__first2)
 468       return -1;
 469     if (*__first2 < *__first1)
 470       return 1;
 471     ++__first1;
 472     ++__first2;
 473   }
 474   if (__first2 == __last2) {
 475     return !(__first1 == __last1);
 476   }
 477   else {
 478     return -1;
 479   }
 480 }
 481
 482 inline int
 483 __lexicographical_compare_3way(const unsigned char* __first1,
 484                                const unsigned char* __last1,
 485                                const unsigned char* __first2,
 486                                const unsigned char* __last2)
 487 {
 488   const ptrdiff_t __len1 = __last1 - __first1;
 489   const ptrdiff_t __len2 = __last2 - __first2;
 490   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
 491   return __result != 0 ? __result
 492                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
 493 }
 494
 495 inline int
 496 __lexicographical_compare_3way(const char* __first1, const char* __last1,
 497                                const char* __first2, const char* __last2)
 498 {
 499 #if CHAR_MAX == SCHAR_MAX
 500   return __lexicographical_compare_3way(
 501                                 (const signed char*) __first1,
 502                                 (const signed char*) __last1,
 503                                 (const signed char*) __first2,
 504                                 (const signed char*) __last2);
 505 #else
 506   return __lexicographical_compare_3way((const unsigned char*) __first1,
 507                                         (const unsigned char*) __last1,
 508                                         (const unsigned char*) __first2,
 509                                         (const unsigned char*) __last2);
 510 #endif
 511 }
 512
 513 template <class _InputIter1, class _InputIter2>
 514 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 515                                  _InputIter2 __first2, _InputIter2 __last2)
 516 {
 517   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
 518 }
 519
 520 __STL_END_NAMESPACE
 521
 522 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
 523
 524 // Local Variables:
 525 // mode:C++
 526 // End: