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: 527