SGISTL.zip_sgi stl_sgistl_sgistl hash_m_sgistl windows

/* * * 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. */ #ifndef ALGO_H #define ALGO_H #include <stdlib.h> #include <limits.h> #include <algobase.h> #include <heap.h> #include <tempbuf.h> 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) { while (first != last) 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) { while (first != last) if (*first++ == value) ++n; } template <class InputIterator, class Predicate, class Size> void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n) { while (first != last) if (pred(*first++)) ++n; } 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++) if (d1-- == d2) return last1; else { current1 = ++first1; current2 = first2; } return (current2 == last2) ? first1 : last1; } 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++)) if (d1-- == d2) return last1; else { current1 = ++first1; current2 = first2; } return (current2 == last2) ? first1 : last1; } 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 ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) { while (first1 != last1) iter_swap(first1++, first2++); return first2; } template <class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op) { while (first != last) *result++ = op(*first++); return result; } template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op) { while (first1 != last1) *result++ = binary_op(*first1++, *first2++); return result; } template <class ForwardIterator, class T> void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value) { while (first != last) { if (*first == old_value) *first = new_value; ++first; } } template <class ForwardIterator, class Predicate, class T> void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value) { while (first != last) { if (pred(*first)) *first = new_value; ++first; } } template <class InputIterator, class OutputIterator, class T> OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value) { while (first != last) { *result++ = *first == old_value ? new_value : *first; ++first; } return result; } template <class Iterator, class OutputIterator, class Predicate, class T> OutputIterator replace_copy_if(Iterator first, Iterator last, OutputIterator result, Predicate pred, const T& new_value) { while (first != last) { *result++ = pred(*first) ? new_value : *first; ++first; } return result; } template <class ForwardIterator, class Generator> void generate(ForwardIterator first, ForwardIterator last, Generator gen) { while (first != last) *first++ = gen(); } template <class OutputIterator, class Size, class Generator> OutputIterator generate_n(OutputIterator first, Size n, Generator gen) { while (n-- > 0) *first++ = gen(); return first; } template <class InputIterator, class OutputIterator