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 63template <class _ForwardIter1, class _ForwardIter2, class _Tp> 64inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) { 65 _Tp __tmp = *__a; 66 *__a = *__b; 67 *__b = __tmp; 68} 69 70template <class _ForwardIter1, class _ForwardIter2> 71inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) { 72 __iter_swap(__a, __b, __VALUE_TYPE(__a)); 73} 74 75template <class _Tp> 76inline 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 90template <class _Tp> 91inline const _Tp& min(const _Tp& __a, const _Tp& __b) { 92 return __b < __a ? __b : __a; 93} 94 95template <class _Tp> 96inline const _Tp& max(const _Tp& __a, const _Tp& __b) { 97 return __a < __b ? __b : __a; 98} 99 100#endif /* __BORLANDC__ */ 101 102template <class _Tp, class _Compare> 103inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) { 104 return __comp(__b, __a) ? __b : __a; 105} 106 107template <class _Tp, class _Compare> 108inline 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 123template <class _InputIter, class _OutputIter, class _Distance> 124inline _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 133template <class _RandomAccessIter, class _OutputIter, class _Distance> 134inline _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 146template <class _Tp> 147inline _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 155template <class _InputIter, class _OutputIter, class _BoolType> 156struct __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 165template <class _Tp> 166struct __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 173template <class _Tp> 174struct __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 181template <class _InputIter, class _OutputIter> 182inline _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 193template <class _InputIter, class _OutputIter> 194inline _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 202inline char* copy(const char* __first, const char* __last, char* __result) { 203 memmove(__result, __first, __last - __first); 204 return __result + (__last - __first); 205} 206 207inline 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 218template <class _BidirectionalIter1, class _BidirectionalIter2, 219 class _Distance> 220inline _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 231template <class _RandomAccessIter, class _BidirectionalIter, class _Distance> 232inline _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 250template <class _BidirectionalIter1, class _BidirectionalIter2, 251 class _BoolType> 252struct __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 266template <class _Tp> 267struct __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 276template <class _Tp> 277struct __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 285template <class _BI1, class _BI2> 286inline _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 296template <class _BI1, class _BI2> 297inline _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 308template <class _InputIter, class _Size, class _OutputIter> 309pair<_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 320template <class _RAIter, class _Size, class _OutputIter> 321inline 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 329template <class _InputIter, class _Size, class _OutputIter> 330inline 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 336template <class _InputIter, class _Size, class _OutputIter> 337inline pair<_InputIter, _OutputIter> 338copy_n(_InputIter __first, _Size __count, _OutputIter __result) { 339 return __copy_n(__first, __count, __result); 340} 341 342//-------------------------------------------------- 343// fill and fill_n 344 345 346template <class _ForwardIter, class _Tp> 347void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) { 348 for ( ; __first != __last; ++__first) 349 *__first = __value; 350} 351 352template <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 362template <class _InputIter1, class _InputIter2> 363pair<_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 373template <class _InputIter1, class _InputIter2, class _BinaryPredicate> 374pair<_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 385template <class _InputIter1, class _InputIter2> 386inline 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 394template <class _InputIter1, class _InputIter2, class _BinaryPredicate> 395inline 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 407template <class _InputIter1, class _InputIter2> 408bool 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 420template <class _InputIter1, class _InputIter2, class _Compare> 421bool 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 434inline bool 435lexicographical_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 446inline 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 462template <class _InputIter1, class _InputIter2> 463int __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 482inline 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 495inline 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 513template <class _InputIter1, class _InputIter2> 514int 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