stl-SGI-30.zip

/* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /* NOTE: This is an internal header file, included by other STL headers. * You should not attempt to use it directly. */ #ifndef __SGI_STL_INTERNAL_ALGO_H #define __SGI_STL_INTERNAL_ALGO_H #include <stl_heap.h> __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma set woff 1209 #endif template <class T> inline const T& __median(const T& a, const T& b, const T& c) { if (a < b) if (b < c) return b; else if (a < c) return c; else return a; else if (a < c) return a; else if (b < c) return c; else return b; } template <class T, class Compare> inline const T& __median(const T& a, const T& b, const T& c, Compare comp) { if (comp(a, b)) if (comp(b, c)) return b; else if (comp(a, c)) return c; else return a; else if (comp(a, c)) return a; else if (comp(b, c)) return c; else return b; } template <class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f) { for ( ; first != last; ++first) f(*first); return f; } template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value) { while (first != last && *first != value) ++first; return first; } template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred) { while (first != last && !pred(*first)) ++first; return first; } template <class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) { if (first == last) return last; ForwardIterator next = first; while(++next != last) { if (*first == *next) return first; first = next; } return last; } template <class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred) { if (first == last) return last; ForwardIterator next = first; while(++next != last) { if (binary_pred(*first, *next)) return first; first = next; } return last; } template <class InputIterator, class T, class Size> void count(InputIterator first, InputIterator last, const T& value, Size& n) { for ( ; first != last; ++first) if (*first == value) ++n; } template <class InputIterator, class Predicate, class Size> void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n) { for ( ; first != last; ++first) if (pred(*first)) ++n; } #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value) { typename iterator_traits<InputIterator>::difference_type n = 0; for ( ; first != last; ++first) if (*first == value) ++n; return n; } template <class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred) { typename iterator_traits<InputIterator>::difference_type n = 0; for ( ; first != last; ++first) if (pred(*first)) ++n; return n; } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ template <class ForwardIterator1, class ForwardIterator2, class Distance1, class Distance2> ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Distance1*, Distance2*) { Distance1 d1 = 0; distance(first1, last1, d1); Distance2 d2 = 0; distance(first2, last2, d2); if (d1 < d2) return last1; ForwardIterator1 current1 = first1; ForwardIterator2 current2 = first2; while (current2 != last2) if (*current1 == *current2) { ++current1; ++current2; } else { if (d1 == d2) return last1; else { current1 = ++first1; current2 = first2; --d1; } } return first1; } template <class ForwardIterator1, class ForwardIterator2> inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) { return __search(first1, last1, first2, last2, distance_type(first1), distance_type(first2)); } template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate, class Distance1, class Distance2> ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred, Distance1*, Distance2*) { Distance1 d1 = 0; distance(first1, last1, d1); Distance2 d2 = 0; distance(first2, last2, d2); if (d1 < d2) return last1; ForwardIterator1 current1 = first1; ForwardIterator2 current2 = first2; while (current2 != last2) if (binary_pred(*current1, *current2)) { ++current1; ++current2; } else { if (d1 == d2) return last1; else { current1 = ++first1; current2 = first2; --d1; } } return first1; } template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred) { return __search(first1, last1, first2, last2, binary_pred, distance_type(first1), distance_type(first2)); } template <class ForwardIterator, class Integer, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value) { if (count <= 0) return first; else { first = find(first, last, value); while (first != last) { Integer n = count - 1; ForwardIterator i = first; ++i; while (i != last && n != 0 && *i == value) { ++i; --n; } if (n == 0) return first; else first = find(i, last, value); } return last; } } template <class ForwardIterator, class Integer, class T, class BinaryPredicate> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value, BinaryPredicate binary_pred) { if (count <= 0) return first; else { while (first != last) { if (binary_pred(*first, value)) break; ++first; } while (first != last) { Integer n = count - 1; ForwardIterator i = first; ++i; while (i != last && n != 0 && binary