algo.h

C++标准库源代码_C++ STL Source Code 请不要修改任何文件

/*
 *
 * 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.
 *
 */

#ifndef ALGO_H
#define ALGO_H

#include <stdlib.h>
#include <bool.h>
#include <pair.h>
#include <iterator.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, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last,
			   OutputIterator result, const T& value) {
    while (first != last) {
	if (*first != value) *result++ = *first;
	++first;
    }
    return result;
}

template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last,
			      OutputIterator result, Predicate pred) {
    while (first != last) {
	if (!pred(*first)) *result++ = *first;
	++first;
    }
    return result;
}

template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
		       const T& value) {
    first = find(first, last, value);
    ForwardIterator next = first;
    return first == last ? first : remove_copy(++next, last, first, value);
}

template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
			  Predicate pred) {
    first = find_if(first, last, pred);
    ForwardIterator next = first;
    return first == last ? first : remove_copy_if(++next, last, first, pred);
}

template <class InputIterator, class ForwardIterator>
ForwardIterator __unique_copy(InputIterator first, InputIterator last,
			      ForwardIterator result, forward_iterator_tag) {
    *result = *first;
    while (++first != last)
        if (*result != *first) *++result = *first;
    return ++result;
}

template <class InputIterator, class BidirectionalIterator>
inline BidirectionalIterator __unique_copy(InputIterator first, 
					   InputIterator last,
			            	   BidirectionalIterator result, 
				    	   bidirectional_iterator_tag) {
    return __unique_copy(first, last, result, forward_iterator_tag());
}

template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator __unique_copy(InputIterator first, 
					  InputIterator last,
			           	  RandomAccessIterator result, 
				   	  random_access_iterator_tag) {
    return __unique_copy(first, last, result, forward_iterator_tag());
}

template <class InputIterator, class OutputIterator, class T>
OutputIterator __unique_copy(InputIterator first, InputIterator last,
			     OutputIterator result, T*) {
    T value = *first;
    *result = value;
    while (++first != last)
	if (value != *first) {
	    value = *first;
	    *++result = value;
	}
    return ++result;
}

template <class InputIterator, class OutputIterator>
inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
                             	    OutputIterator result, 
				    output_iterator_tag) {
    return __unique_copy(first, last, result, value_type(first));
}

template <class InputIterator, class OutputIterator>
inline OutputIterator unique_copy(InputIterator first, InputIterator last,
			   	  OutputIterator result) {
    if (first == last) return result;
    return __unique_copy(first, last, result, iterator_category(result));
}
template <class InputIterator, class ForwardIterator, class BinaryPredicate>
ForwardIterator __unique_copy(InputIterator first, InputIterator last,
			      ForwardIterator result, 
			      BinaryPredicate binary_pred,
			      forward_iterator_tag) {
    *result = *first;
    while (++first != last)
        if (!binary_pred(*result, *first)) *++result = *first;
    return ++result;
}

template <class InputIterator, class BidirectionalIterator,
          class BinaryPredicate>
inline BidirectionalIterator __unique_copy(InputIterator first, 
					   InputIterator last,
			            	   BidirectionalIterator result, 
					   BinaryPredicate binary_pred,
				    	   bidirectional_iterator_tag) {
    return __unique_copy(first, last, result, binary_pred,
			 forward_iterator_tag());
}

template <class InputIterator, class RandomAccessIterator,
          class BinaryPredicate>
inline RandomAccessIterator __unique_copy(InputIterator first, 
					  InputIterator last,
			           	  RandomAccessIterator result, 
					  BinaryPredicate binary_pred,
				   	  random_access_iterator_tag) {
    return __unique_copy(first, last, result, binary_pred, 
			 forward_iterator_tag());
}

template <class InputIterator, class OutputIterator, class BinaryPredicate,
          class T>
OutputIterator __unique_copy(InputIterator first, InputIterator last,
			     OutputIterator result,
			     BinaryPredicate binary_pred, T*) {
    T value = *first;
    *result = value;
    while (++first != last)
	if (!binary_pred(value, *first)) {
	    value = *first;
	    *++result = value;
	}
    return ++result;
}

template <class InputIterator, class OutputIterator, class BinaryPredicate>
inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
                             	    OutputIterator result,
				    BinaryPredicate binary_pred,
				    output_iterator_tag) {
    return __unique_copy(first, last, result, binary_pred, value_type(first));
}

template <class InputIterator, class OutputIterator, class BinaryPredicate>
inline OutputIterator unique_copy(InputIterator first, InputIterator last,